算法的时间复杂度和空间复杂度

目录

1 如何衡量一个算法的好坏

2.时间复杂度

2.1 时间复杂度的概念

2.2 大O的渐进表示法

2.3常见代码举例

 2.3.1 Func2        O(N)

 2.3.2 Func3        O(M+N)

 2.3.3 Func4        O(1)

 2.3.4 Func5    strchr   O(N)

 2.3.5 Func6   冒泡排序     O(N^2)

 2.3.6 Func7 二分查找(折半查找）        

 2.3.7 Func8阶乘递归        O(N)

 2.3.8 Func9斐波那契递归        O(N)

3 空间复杂度

3.1 Func1冒泡排序        O(1)

3.2 Func2斐波拉契数列        O(N)

3.3 Func3阶乘函数         O(N)

3.4 Func4 区分不同调用下的空间开辟

 3.4.1

 3.4.2​

3.5 Func5 Fib

4.常见复杂度

---

1 如何衡量一个算法的好坏

        算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般 是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

        时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2.时间复杂度

2.1 时间复杂度的概念

        时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一 个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度

Func1 执行的基本操作次数 ：

F(N)=+2*N+10 

        N = 10 F(N) = 130

        N = 100 F(N) = 10210

        N = 1000 F(N) = 1002010

        实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

2.2 大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后，Func1的时间复杂度为：

O()

        N = 10 F(N) = 100

        N = 100 F(N) = 10000

        N = 1000 F(N) = 1000000

        通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

2.3常见代码举例

2.3.1 Func2        O(N)

 2.3.2 Func3        O(M+N)

 2.3.3 Func4        O(1)

 2.3.4 Func5    strchr   O(N)

 

有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

 

 2.3.5 Func6   冒泡排序     O(N^2)

最好：O(N);

(数组位置不清楚是否有序，所以至少要对相邻的两个数相互比较一次，至少比较n-1次）

最坏：O(N^2);

（第一轮比较n-1次，第二轮比较n-2次，……比较2次，最后剩最末的一对数，比较1次，等差数列 ）

2.3.6 Func7 二分查找(折半查找）        O（）

最好：O（1）；

最坏：（不好写，在时间复杂度中，只有以2为底的才能简化为logN，其他底数不能简写，有些地方简写为lgN,但是我们不推荐这样写）

 

2.3.7 Func8阶乘递归        O(N)

 基本操作递归了N+1次，时间复杂度为O(N)

2.3.8 Func9斐波那契递归        O(N)

 现基本操作递归了2^N次，时间复杂度为O(2^N)

 2^30 10亿

2^40  10000亿

2^50  1亿亿

3 空间复杂度

        空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用（额外）存储空间大小的量度 。

        空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。

        空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

3.1 Func1冒泡排序        O(1)

 创建了红色框的三个变量，常数个变量，O(1);

3.2 Func2斐波拉契数列        O(N)

         额外开辟一个数组，O(N);malloc开n+1个空间，从0-n,n+1个

3.3 Func3阶乘函数         O(N)

 

 

3.4 Func4 区分不同调用下的空间开辟

 3.4.1

 3.4.2

 即递归空间开辟原理

3.5 Func5 Fib

前面我们讲过Fib时间复杂度是O(2^N)

                           空间复杂度呢？O(N)

4.常见复杂度