【数据机构】_复杂度
目录
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/145165702
https://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;
else
return 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)（二维数组）；