目录
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语言查找字符-****博客文章浏览阅读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.****.net/m0_63299495/article/details/145165702https://blog.****.net/m0_63299495/article/details/145165702https://blog.****.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)（二维数组）；