【数据结构】_复杂度

目录

1. 算法效率

2. 时间复杂度

2.1 时间复杂度概念

2.2 准确的时间复杂度函数式

2.3 大O渐进表示法

2.4 时间复杂度的常见量级

2.5 时间复杂度示例

3. 空间复杂度

3.1 空间复杂度概念

3.2 空间复杂度示例

---

1. 算法效率

一般情况下，衡量一个算法的好坏是从时间和空间两个维度来衡量的。

时间复杂度主要衡量一个算法的运行快慢，空间复杂度主要衡量一个算法运行需要的额外空间。

2. 时间复杂度

2.1 时间复杂度概念

在计算机科学中算法的时间复杂度是一个函数，一个算法所花费的时间与其中语句的执行次数成比例，算法中的基本操作的执行次数，为算法的时间复杂度。

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

注：不能直接用运行时间来定义一个算法的时间复杂度，一个算法的运行时间与硬件的配置存在联系，同样一个算法无法算出准确时间。而时间复杂度与具体机器无关。

2.2 准确的时间复杂度函数式

对于以下代码：

void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

F(N)=N*N+2*N+10，这是准确的时间复杂度函数式，计算的结果是算法运行的准确次数。

但其意义并不大，计算时间复杂度时，并不一定要计算出准确的执行次数，只需要大概执行次数表示算法效率所在量级即可，故而引进大O的渐进表示法。

2.3 大O渐进表示法

当不方便在算法之间比较准确时间复杂度函数式时，使用大O的渐进表示法对其进行简化。

简单而言，大O渐进表示法是估算一个算法的数量级而非准确数值。

具体而言，推导大O阶方法：

（1）用常数1取代运行时间中的所有加法常数；（O(1)代表常数次，而非1次）

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

（3）如果最高阶项存在且不是1，则去除与这个项目相乘的常数。

得到的结果就是大O阶。

2.4 时间复杂度的常见量级

按数量级递增排列，常见的时间复杂度有：

O(1)<=O(log N)<=O(N)<=O(Nlog N)<=O(n^2)<=O(n^3)<=...<=n^k<=O(2^n)

随着问题规模N的不断增大，上述时间复杂度不断增大，算法的执行效率越低，若复杂度超过O(N^3)则该算法效率已经非常低，没有运行的必要。

2.5 时间复杂度示例

示例1：

void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

时间复杂度为O(N）=N；（时间复杂度准确函数式：F(N)=2*N+10）

示例2：

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\n", count);
}

当N、M大小未知时，时间复杂度表示为O(N+M)；

当N远大于M时，时间复杂度表示为O（N）；

当M远大于N时，时间复杂度表示为O（M）；

当N、M属于一个量级时，时间复杂度表示为O（M）或O(N)均可；

示例3：

void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

时间复杂度表示为O(1)；

示例4：

const char * strchr ( const char * str, int character );

该算法的时间复杂度最好1次，最坏N次，时间复杂度一般看最坏情况，为O（N）；

注：（1）strstr为字符串查找函数，详细内容见下文：

【C语言】_字符串查找函数strstr_c语言查找字符-CSDN博客文章浏览阅读147次，点赞9次，收藏5次。注：关于上文strstr函数的模拟实现，还有很大优化空间，包括但不限于KMP算法，本篇仅实现简单的匹配功能，暂不考虑效率。（2）待匹配字符串str2需逐字符在str1中进行对应查找匹配，将用于遍历str2的指针变量记为s2，类型为char*；（3）str2需与str1中的字符逐字符进行匹配，需设遍历str1的指针变量，记为s1，类型为char*；（1）返回值为第一次匹配的str2在str1中的位置，记为cur，类型为char*；strstr函数功能：在str1中查找str2；若未找到，则返回空指针；_c语言查找字符https://blog.csdn.net/m0_63299495/article/details/145165702https://blog.csdn.net/m0_63299495/article/details/145165702https://blog.csdn.net/m0_63299495/article/details/145165702（2）在算法时间复杂度计算时，一般会采取保守估计，将最坏情况作为时间复杂度。

最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)；

示例5：（冒泡排序）

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;}
}

时间复杂度准确函数式式F(N) = N-1+N-2+...+2+1=((N-1+1)*(N-1))/2=(N*(N-1))/2;

故时间复杂度为O(N^2)；

示例6：（二分查找）

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;elsereturn mid;}return -1;
}

二分查找用于有序数组的查找，查找区间变化为N -> N/2 -> N/2/2 -> N/2/2/2 -> ...  -> N/2/2/.../2

① 查找的最好情况为查找一次即找到，即O（1）；

② 查找的最坏情况为查找区间只剩一个数或没找到，即 N/2/2/.../2=1，假设查找了x次，即2^x=N，求得最坏情况为O(log N)   ，故时间复杂度为O(log N) ；

注：在时间复杂度的表示中，log₂N 可简写为 log N，不准确表达也有lg N。

在时间复杂度表示中，默认 log N 的底数为2。

示例7：（阶乘）

long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

Fac(N)调用Fac(N-1)， Fac(N-1)调用Fac(N-2)...Fac(2)调用Fac(1)，Fac(1)调用Fac(0)，共调用N+1次，且单次调用复杂度为O(1)，递归的时间复杂度是所有递归调用次数的累加：

故时间复杂度为O(N);

示例8：

long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

 复杂度具体函数可以近似为Fib(N)=2^0 + 2^1 + 2^2 + ...... + 2^(N-2) = 2^(N-1) - 1:

时间复杂度为O(2^N);（仅有理论意义，实际几乎不用）

注：当N不是非常大时，通常使用循环代替递归计算斐波那契数列，可降低时间复杂度为O(N)：

long long Fib(size_t N) {long long f1 = 1;long long f2 = 2;long long f3 = 0;for (size_t i = 3; i <= N; i++) {f3 = f1 + f2;f1 = f2;f2 = f3;}return f3;
}

3. 空间复杂度

3.1 空间复杂度概念

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

同时间复杂度一样，具体占用了多少字节的空间大小没有意义，也采用大O渐进表示法，空间复杂度计算的是变量个数。

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

3.2 空间复杂度示例

示例1：

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;}
}

该程序开辟了常数个额外空间，空间复杂度是O(1);

示例2：

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;
}

空间复杂度是O(N)；

示例3：

long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

递归调用了N+1次，量级为N，开辟了N个栈帧，每个栈帧使用了常数个空间，空间复杂度为O(N)；

示例4：

long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

（时间是累积的；空间不累积，可以重复利用）空间复杂度是O(N)； 

相较于时间复杂度，空间复杂度更为简单，通常情况下最常见的空间复杂度有O(1)、O(N)（一维数组）、O(N^2)（二维数组）；