数据结构中计算时间复杂度技巧（数据结构-时间复杂度和空间复杂度）

一：算法效率-时间和空间复杂度

完成一个功能可能会有多种算法，因此算法也就有了优劣之分。正如我们用速度描述物体的快慢一样，我们用复杂度来评判一个算法是好还是坏。算法的复杂度分为时间复杂度和空间复杂度，由于现代计算机发展非常快，除一些极端情况外，一般无需考虑空间复杂度，所以我们关心的还是算法的复杂度，通俗点说，就是这个算法够不够快。

二：时间复杂度（1）时间复杂度的概念

从字面意思上看，时间复杂度就是指某个算法执行了多长时间。但是，我们描述时间复杂度时却从来不用具体的运行时间，因为使用具体的运行时间来描述一个算法的时间复杂度是没有任何参考意义的，一个算运行在普通电脑和超级计算机上，时间肯定是有巨大区别的，这就不禁产生一个疑问，运行时间短的算法究竟是占了物理机运算速度优势还是说这个算法本身效率就很高？所以为了让这个时间复杂度更具有“权威性”，“通用性”，我们用算法中的基本操作的执行次数来描述时间复杂度。

A：例子

且看如下代码，请计算它的执行次数

void Fun1(int N) { int count = 0; for (int i = 0; i < N; i )//总共N次 { for (int j = 0; j < N; j ) { count ; } } } for (int k = 0; k < 2 * N; k)//总共2N次 { count ; } int M = 10; while (M--)//总共10次 { count ; } printf("%d ", count);

可以很容易计算出的它的执行次数为N^2 2*N 10用函数表示为F(N)=N^2 2*N 10

B：大O的渐进表示法

上面函数中如果“N”取值很小，那么常数项，一次项的改变都能起到“举足轻重”的效果。但是当“N”取值很大时，常数项和一次项就显得“微乎其微”了。所以上述算法的复杂度不能那样描述，应该用大O的渐进表示法。

推导过程：

• 用常数1取代运行时间中的所有加法常数。
• 在修改后的运行次数函数中，只保留最高阶项。
• 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶（也就是说N2和2N2是一样的）

于是经过推导，上述例子中的算法时间复杂度为O(N^2)

3）最好最坏情况

有些算法是有“概率“的，也就是不确定性。比如顺序查找，其在查找过程中有可能第一次就找到了，也有可能第二次找到，还有可能第N次找到。如果是第一次就找到了，很显然使是这个算法的最好情况，如果是第N次找见那么就是它的最坏情况，这样一般情况（平均情况）就是N/2次。而我们在描述算法的复杂度给出的是最坏情况，因为这已经是最坏的了，那么剩余的情况肯定就这个好

（4）例子

实例一：

// 计算Func2的时间复杂度？ void Func2(int N) { int count = 0; for (int k = 0; k < 2 * N ; k) { count; } int M = 10; while (M--) { count; } printf("%d ", count); }

时间复杂度为：O(N)

实例二：

// 计算Func3的时间复杂度？ void Func3(int N, int M) { int count = 0; for (int k = 0; k < M; k) { count; } for (int k = 0; k < N ; k) { count; } printf("%d ", count); }

若M远大于N则为：O(N)

实例三：

// 计算Func4的时间复杂度？ void Func4(int N) { int count = 0; for (int k = 0; k < 100; k) { count; } printf("%d ", count); }

注意忽略常数项：O(1)

实例四：

// 计算BubbleSort的时间复杂度？ void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }

上述是冒泡排序的代码，这里要注意一点，不要认为嵌套循环的时间复杂度复杂度就是每次循环的次数之积。对于冒泡排序而言，每次排序，都把一个大数排到了最后，所以每趟排序结束之后，下次比较次数就减少一次，也就是1 2 3 4 5 6 ····· N-1,这是一个等差数列，计算其前N项和，得最坏情况的复杂度为O(N^2) ，相应的最好情况就是O（N）

实例五：

// 计算BinarySearch的时间复杂度？ int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n-1; while(begin<end) { int mid=begin ((end-begin)>>1); if(a[mid]<x) begin=mid 1; else if(a[mid<x]) end=mid; else return mid; } return -1; }

这是二分查找算法，计算复杂度时不要被循环给误导了，计算时要领会算法的思想。二分查找在查找顺序表时，每次舍弃一半元素，查找一个元素就不断除以2，不断除以2，这样反向过来计算，想要查找到一个长度为N的顺序表中的某个元素时次数就是log2N，那么复杂度就O(log2N)

实例六

long long Factorial(size_t N) { return N < 2 ? N : Factorial(N-1)*N; }

这是使用递归计算N的阶乘对于递归算法，其时间复杂度为：递归次数*每次递归的次数。故该算法的时间复杂度为O(N)。

实例七

// 计算斐波那契递归Fibonacci的时间复杂度？ long long Fibonacci(size_t N) { return N < 2 ? N : Fibonacci(N-1) Fibonacci(N-2); }

这是斐波那契数列的递归算法计算Fib(N)，就要计算Fib(N-1) Fib(N-2)，同理要计算Fib(N-1)就要计算Fib(N-2) Fib(N-3)，计算Fib(N-2)就要计算Fib(N-3) Fib(N-4)·······比如N=5时，可以画出这样形象的图

学完二叉树后，就可以知道这是一颗满二叉树，对于一颗满二叉树每层高度上的结点数(这里结点数就代表斐波那契递归算法递归一次)为2k-1(这里的k指的是高度)，每层结点数加起来结果就是2n-1（这里n指的是结点总数），于是斐波那契递归算法的时间复杂度为O(2^N)这里要注意一下，斐波那契算法生成的满二叉树并不是真正的二叉树，上图中得到很明显的展示，右上角一定会要比左下角的先到1，但是对整体的时间复杂度并没有太大影响。可以发现计算斐波那契如果使用递归的算法，那么当N比较大时，时间复杂度将会指数级的增长，而且采用这种算法在计算时其实有一部分计算时完完全全重复了，完全就是在做无用功。所以我们可以采用迭代的方式实现

#include <stdio.h> #include <stdio.h> #include <stddef.h> long long* Fibonacci(size_t N) { long long* fibArray = (long long*)malloc(sizeof(long long)*(N 1)); if (fibArray==NULL) { return -1; } fibArray[0] = 0; if (N == 0) return fibArray; fibArray[1] = 1; for (int i = 2; i <= N; i ) { fibArray[i] = fibArray[i - 1] fibArray[i - 2]; } return fibArray[N]; } int main() { printf("%d ", Fibonacci(50)); }

三：空间复杂度

时间复杂度不计算具体的时间，只算大概执行了多少次空间复杂度不计算具体占用的空间，只计算大概定义的变量个数实例一

// 计算BubbleSort的空间复杂度？ void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }

共定义了5个变量，故空间复杂度为O(1).

实例二

long long* Fibonacci(size_t n) { if (n == 0) return NULL; long long * fibArray = (long long *)malloc((n 1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n; i) { fibArray[i] = fibArray[i - 1] fibArray[i - 2]; } return fibArray; }

斐波那契数列开辟了N 1个空间，故空间复杂度为O(N)

实例三

// 计算阶乘递归Factorial的空间复杂度？ long long Factorial(size_t N) { return N < 2 ? N : Factorial(N - 1)*N; }

阶乘的递归算法递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

,