【数据结构】时间复杂度与空间复杂度

目录

时间复杂度

空间复杂度

---

时间复杂度

算法的时间复杂度并不是指一个代码运行时间的快慢，因为在不同机器上运行的时间肯定不同，因此算法的时间复杂度指的是基本操作的执行次数，他是一个数学意义上的函数。这个函数并不是C语言中那种函数，而是一个数学函数，比如

显然是执行了N方+2N+10次，这个N方假设我们说他是F(N),也就是一个数学函数，那么这个F(N)就是上面这个算法的时间复杂度。但是实际上我们并不一定要计算精确的执行次数，而只需要大概执行次数，因为当N足够大的时候，F(N)的大小主要是由N方决定了，因此我们就可以用N方来近似这个表达式的值。 我们可以使用大O的渐进表示法。

大O渐进表示法的规则如下：

1、用常数1取代运行时间中的所有加法常数。比如要运行一万次是O(1),一亿次也是写作O(1),这是因为CPU的功能很强大，对于我们能写出来的这些常数，在CPU看来都一样，都是瞬间搞定。

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

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。换句话说如果保留的最高阶数系数不是1，通通都写成系数是1，也就是说不管最终决定运算次数的项是2N，3N,1000N，使用大O渐进表示法都写作O(N),如果最后算出来运算次数是2的n-1次方，n-2次方等等，那么时间复杂度是O(2^n)

4.有些算法的时间复杂度存在最好、平均和最坏情况：最坏情况：任意输入规模的最大运行次数(上界)平均情况：任意输入规模的期望运行次数最好情况：任意输入规模的最小运行次数(下界)例如：在一个长度为N数组中搜索一个数据x最好情况：1次找到最坏情况：N次找到平均情况：N/2次找到。在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

下面来计算一下冒泡排序的时间复杂度

执行的次数也就是for循环一共循环了多少次，可以看到第一次要比较n-1个，第二次要比较n-2个，第n-1次要比较1个，一共执行的次数就是这些全加起来，等差数列求和，因此一共是n(n-1)/2,最高次数是2次方，虽然有系数二分之一，但是要忽略掉，因此他的时间复杂度是O(n方)

注：只是在本例中执行次数就是循环次数，并不是说所有代码的执行次数都是循环次数

计算二分查找的时间复杂度

二分查找的思想就是一次去掉一半，实际上有可能是一次找到了，也有可能是找到剩下最后一个了也没找到，要计算复杂度，我们就要考虑最坏情况，最坏情况就是找到了剩下最后一个元素，这就是最后一次，不管最后剩下的这个元素是不是我们要找的元素，都不会再执行了，假设有n个数，找了x次最后剩下一个了，实际上x就是复杂度，那么x能不能用已知条件表示呢？N除了x个2变成了1，换句话说1乘上x个2也就是2的x次方等于n，x也就是以二为底n的对数，因此二分查找的时间复杂度是以二为底n的对数。

阶乘递归的时间复杂度

第一次调用Fac(N),而Fac(N)又会调用Fac(N-1)，以此类推直到Fac(1)调用Fac(0)，就开始一直返回了，因此实际基本语句执行了N+1次，时间复杂度是O(N)

把代码稍作修改，这次时间复杂度是多少？

仍然是Fac(N)调用Fac(N-1)，Fac(N-1)调用Fac(N-2)以此类推直到Fac(1)调用Fac(0)，但是在每次调用之前都有一个循环语句，在Fac(N)里执行了N次，在Fac(N-1)里执行了n-1次......在Fac(1)里执行了1次，因此基本操作一共执行了N(N+1)/2次，所以时间复杂度是O(N方)

计算斐波那契递归的时间复杂度

一生二，二生四，直到调用参数是2或者1的时候才可以返回值，因此右边的会先开始返回值，左边的后返回，最终形状大概是缺一块的三角形

形状类似这样

假设是一个满的三角形，那么最终应该有2的零次方一直加到2的N-2次方，这样一个等比数列求和，结果是2的N-1次方-1，实际上没有什么多项，还应该减去这个灰色的三角形，但是当N足够大的时候，实际上这个灰色三角形非常的小，可以忽略不计，因为复杂度考虑的是量级，是一个大约的数，因此我们就用这个完整三角形形状的个数来表示，因此斐波那契递归的时间复杂度是O(2^N)

空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度， 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

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

计算冒泡排序的空间复杂度

在冒泡排序中，为了给传给我们的数组排序而额外创建的变量就只有end，exchange，i等等，也就是常数个，因此冒泡排序的空间复杂度是O(1)

创建了n+1个变量，因此空间复杂度是n+1，写作O(n+1)，可能疑问就是这不是开辟了能放n+1个long long类型的空间吗，怎么就开辟变量了，这虽然是个指针，指针变量的名字实际上就相当于一个数组名，申请空间相当于是创建了一个数组，我可以使用[]操作符来访问这块空间的元素，比如fibArray[1]就访问了第二个元素，这不就是创建变量吗？

实际上我们在求空间复杂度的时候没有必要每次都紧扣定义创建的变量个数，一般来说就是关注开辟的空间能放多少个变量。

Fac(N)会调用Fac(N-1)以此类对直到Fac(1)调用Fac(0)，一共调用了N+1次，每次里面创建了常数个变量，因此空间复杂度是O(N)

在上面计算过Fib的时间复杂度是O(2^N),也就是说执行了这个量级次基本操作，而每次基本操作创建的变量都是常数个，那是不是说Fib的空间复杂度也是O(2^N)呢？首先说答案：不是。在计算时间复杂度和空间复杂度的时候，我们应该遵循时间是一去不复返的，空间是可以重复利用的。

什么叫空间可以重复利用呢？

首先来说重复利用并不是共用，因为在调用完某个函数的时候，为他申请的栈帧就随之销毁了，何谈共用？

比如有这样一段代码

我们发现这两个变量的地址是相同的，这是因为我们在主函数里面调用了这两个函数，先调用Func1，于是为他开辟了一块栈帧，里面有变量a

Func1调用完成之后，为他开辟的栈帧就被换给了操作系统，俗称栈帧被销毁，然后就开始调用Func2，也要为他开辟一块栈帧，前面通过打印地址我们知道这两个变量的地址是相同的，也就是说为Func2开辟的栈帧也是同一块。这就是空间的重复利用。

再回到Fib函数的空间复杂度计算

假设我们刚上来调用的是Fib(5)

计算这种递归函数的空间复杂度主要就是考虑开辟的栈帧是什么情况，比如我们刚上来调用的是Fib(5),Fib(5)为了得到返回值，就要调用Fib(4)和Fib(3)，那问题来了，先后给Fib(4)和Fib(3)开辟栈帧吗？当然不是，先调用的是Fib(4)，Fib(4)都还没返回呢，那必然不能调用Fib(3)，那就不能为Fib(3)开辟栈帧，而是继续执行Fib(4)，而Fib(4)会调用Fib(3)和Fib(2)，先调用的是Fib(3)，Fib(3)为了得到返回值就会调用Fib(2)和Fib(1)，先调用的是Fib(2)，此时有返回值了，在返回之后为Fib(2)申请的这快栈帧就可以还给操作系统了，有了返回值Fib(2)就算执行完了，那就可以接着调用Fib(1)，从而又要为Fib(1)开辟一块栈帧，这块栈帧和刚才Fib(2)申请的那块是同一块，也能得到一个返回值并把这块栈帧销毁，这样Fib(3)就有值了，就能调用倒数第二行的Fib(2)了，于是为他申请一块栈帧，这快栈帧和刚才调用完Fib(3)被销毁的那块是同一块栈帧，以此类推，最终实际上就只申请了4块栈帧。

于是调用Fib(N)就申请了N-1块栈帧，因为同层的都在重复利用同一块空间，因此Fib的空间复杂度是O(N)。