算法的时间复杂度、空间复杂度如何比较？

目录

一、时间复杂度BigO

大O的渐进表示法：

例题一：

例题2：

例题3：冒泡排序的时间复杂度

例题4：二分查找的时间复杂度

书写对数的讲究：

例题5：

 实例6：

利用时间复杂度解决编程题

​编辑思路一：

思路二：

源码：

思路三：

回顾位操作符

二、空间复杂度详解

概念：

例题1：冒泡排序的空间复杂度是多少？

例题2：单路递归

例题3

解析：

例题4（硬菜，双路递归）

利用空间复杂度解决编程题

思路一：

代码：

思路二：

代码：

思路三：

代码：

---

一、时间复杂度BigO

首先我们不能以机器运行算法的时间来评判一个算法的时间复杂度，因为即使是相同的算法在不同机器上（机器的个体差异性）运行时间都可能不尽相同，因此我们采用

【大O表示法】——算法的渐进复杂度T（n）=O（f（n））。

就是算执行次数！

        首先解读这个公式，f（n）表示代码执行的次数，O表示正比例关系，而T（n）就表示算法的渐进复杂度（就是当一个问题量级增加的时候，算法运行时间增长的一个趋势）。

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

大O的渐进表示法：

实际中我们计算时间复杂度时，我们其实不一定要计算精确的执行次数，而只需要大概执行次数。

大O渐进表示法的规则：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则取出与这个项相乘的常数，使其前面的系数是1，得到的就是大O渐进表达式。
4. 用最坏的情况去考虑计算时间复杂度 。

例题一：

 我们可以计算出++count语句被执行多少次，从而算出该算法的时间复杂度。

不难计算出这样一个数学函数表达式

例题2：

strchr是一个库函数用来计算某个特定字符在字符串中的位置，实现方法就是循环遍历。

这样时间复杂度一共有三种情况：

1、最幸运，遍历一次就找到

2、最不幸，一直遍历到最后才找到

3、取平均值，遍历到中间才找到

以上三种情况，到底哪种是符合时间复杂度的呢？答案是最坏情况！也就是O（N）

下面是更复杂的一些计算时间复杂度的例题。

一些更复杂的代码，我们不能只看代码去计算时间复杂度，我们要看重代码的思想是什么，底层逻辑！

例题3：冒泡排序的时间复杂度

 

 我们首先要计算最坏的情况，那就是数据本来从小到大顺序排列，而要求从大到小排列，所以全部都需要重新排，第一次n-1,第二次n-2,第三次n-3，以此类推直到最后的1，这就是一个等差数列求和，公差是1，计算得出最高次项是N^2，所以最终O(N)=N^2。

那最好的情况是不是O(1)呢？

答案不是，因为如果已经排好序，我们还需要判断是否有序，判断是否有序就需要时间！所以最好的情况就是O(N)

例题4：二分查找的时间复杂度

 二分查找的最坏情况就是我们要查找的数据在边界，查找区间缩放只剩下一个值时，就是最坏。最坏情况下查找了多少次？除了多少次2，就查找了多少次。

假设区间个数是N，/2/2/2/2一直除到最后区间只剩下一个值。

书写对数的讲究：

由于对数在文本中不好写，支持一些展示公式编辑器才方便，所以时间复杂度简写成logN,只有log以2为底N的对数才可以简写成logN,其他都要写出来。

暴力搜索O(N)和二分查找O(logN)量级的天差地别

例题5：

计算阶乘递归的时间复杂度

 注意计算递归的时间复杂度主要看函数被调用的次数，然后再看函数内部的时间复杂度。

递归算法的时间复杂度是多次调用的累加。

我们发现上述代码的递归函数调用了N+1次，而每次函数的内部都是O(1),所以最终的时间复杂度就是O(N).相当于N+1个1的时间复杂度

 实例6：

 跟上面的代码区别是这是一个双路递归，上面是单路递归

 上图是双路递归的调用次数，不难发现规律是以2^n为数量级进行递增，然后再进行等比数列求和，最终计算出来的数量级就是2^n,所以O(N)=2^N

最终的三角形是右下角缺失一块，但并不影响我们的数量级。

但是2^n的时间复杂度算的非常慢，因为CPU能接受是以亿为单位，但是2^n很快就到达CPU的顶峰了。

所以用递归求解斐波那契数列只有理论上可行

利用时间复杂度解决编程题

思路一：

排序+遍历（下一个数不等于下一个数据+1，这个下一个数就是消失的数字）

时间复杂度：O(logN*N)用快排qsort的前提下

思路二：

用0~N等差数列求和公式计算结果减去数组中的值，结果就是消失的数字

时间复杂度：O(N)

源码：

int main()
{int arr[] = { 0,1,3 };int sum = 2 * 3;//求和直接用等差数列的公式计算for (int i=0;i<3;i++){sum -= arr[i];}printf("%d\n", sum);return 0;
}

思路三：

单身狗思路：异或，两个成对出现的数字中，出现了一个单独的数字，用异或去解决

int main()
{int arr[] = { 1,3,4 };int ret = 0;for (int i=1;i<=4;i++){ret ^= i;}for (int i=0;i<3;i++){ret ^= arr[i];}printf("%d\n", ret);return 0;
}

回顾位操作符

^——异或操作符——对应的二进制相同返回0，对应的二进制位不同，就返回1，注意两个相同的数字异或结果是0，任何一个数据与0异或结果就是它本身，并且异或操作符满足交换律

&——按位与操作符——只要有0，结果就是0

|——按位或操作符——只要有1，结果就是1

二、空间复杂度详解

概念：

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

空间复杂度不是程序占用了多少字节的空间，而是计算的是变量的个数，也采用大O渐进表示法。

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

例题1：冒泡排序的空间复杂度是多少？

首先参数传过来的数组不算入空间复杂度，如果我们是为了让这个数组排序，额外创建了一个数组，这样的数组才算入空间复杂度。

这样计算发现只有end，exchange，i是我们额外创建的变量，所以一共是3个，即空间复杂度是O(1)，注意O(1)不代表空间空间复杂度是1个，而是常数个。

例题2：单路递归

不难看出，为了解决题目，代码额外创建了一个数组，所以最后的空间复杂度就是O(N)

例题3

 

解析：

假设有N层递归，每次递归需要调用一次函数，而调用函数需要创立栈帧，每调用一次函数，就需要创建一次栈帧，而创建一次栈帧需要常数个的空间，注意栈帧在函数使用完毕后是会销毁的，但是空间复杂度计算的是最大的空间占用，所以只有当递归结束时才计算整体的栈帧。所以最终的空间复杂度就是O（N）。

例题4（硬菜，双路递归）

 我们首先要明确这样一个原则，时间是累计的，一去不复返，空间是可以重复利用的。

创建和销毁函数栈帧的潜规则

我们先明白这样一个道理，当一个函数调用完毕后，第一个函数创建的栈帧的空间就会返回操作系统，接着继续再调用另外一个函数，第二个函数创建后需要的栈帧空间就是上一个函数的空间，是一模一样的！下面的例子为证，a和b的地址是一样的。

有了上面的基础后，我们还要知道双路递归函数的调用顺序，下图为例。

当我们一路递归调用完毕，函数创建的栈帧销毁，接下来另一个新的函数就会继续用这个空间，重复利用，所以最多额外占用N个空间，即空间复杂度是O(N)。

利用空间复杂度解决编程题

思路一：

先将最后一个数取出来，然后将数组里前面的元素向右移动一位，这样就算是右旋一次，接着进行循环，一共循环k次。

这样的空间复杂度O(1)，时间复杂度O(N^2)，因为考虑最差情况，不能是KN，因为K是一个变量，情况有好有坏，算复杂度直接取最差的情况。

代码：

int main()
{int arr[] = { 1,2,3,4,5,6,7 };int sz = sizeof(arr) / sizeof(arr[0]);int k = 0;scanf("%d", &k);for (int i=0;i<k;i++){int tmp = arr[sz - 1];for (int j=0;j<sz-1;j++){arr[sz - 1 - j] = arr[sz - 2 - j];}arr[0] = tmp;}for (int i=0;i<sz;i++){printf("%d ", arr[i]);}return 0;
}

思路二：

用空间换时间，再开辟一个数组，直接将数据拷贝到新的数组，然后再整体拷贝到原来的数组

时间复杂度就是O(N),因为我们额外开辟了一个数组空间，所以我们的空间复杂度就是O(N)

代码：

int main()
{int arr[] = { 1,2,3,4,5,6,7 };int* tmp = (int*)malloc(sizeof(arr) * sizeof(arr[0]));if (tmp == NULL){perror(malloc);exit(-1);}int k = 0;int sz = sizeof(arr) / sizeof(arr[0]);scanf("%d", &k);//注意memcpy最后一个参数以字节为单位！memcpy(tmp, arr + sz - k % sz, k % sz * sizeof(arr[0]));memcpy(tmp + k % sz, arr, (sz - k % sz) * sizeof(arr[0]));memcpy(arr, tmp, sz * sizeof(arr[0]));for (int i=0;i<sz;i++){printf("%d ", arr[i]);}free(tmp);tmp = NULL;return 0;
}

思路三：

三步翻转法：

空间复杂度是O(1),时间复杂度是O(N)，这就是最优解法！

不容易想到，需要积累！

代码：

void reverse(int* left, int* right)
{while (left <= right){/*int* tmp = left;left = right;right = tmp;*///将两个地址交换int tmp = *left;*left = *right;*right = tmp;left++;right--;}
}int main()
{int arr[] = { 1,2,3,4,5,6,7 };int sz = sizeof(arr) / sizeof(arr[0]);int k = 0;scanf("%d", &k);reverse(arr, arr+sz-k-1);reverse(arr + sz-k, arr + sz - 1);reverse(arr, arr + sz - 1);for (int i=0;i<sz;i++){printf("%d ", arr[i]);}return 0;
}