引入
引入
1、算法竞赛是思维脑力的较量。一道好的算法题可以区分出好的算法程序(可以获得较高得分)和不那么好的算法程序(低分甚至零分)
2、评价算法的优劣是有一套标准的。利用这套标准，可以在动手实践之前即可估计这种写法是否靠谱
3、如果判断这套算法可能超时或超出内存限制而导致无法得分，则应该想想有没有更好的写法
4、接下来便来学习如何评价一套算法
如何评价算法
代码可实现
1、按照编程者的能力可以将算法通过代码实现出来
2、如果想出算法但无法实现，或者需要花费非常多的时间和行数(甚至超出比赛时间)才能编写，显然是不行的结果正确
1、程序能够运行完毕，不会在运行过程中出错崩溃
2、输出的结果必须符合期望，通过测试点能在限定时间内运行完毕
1、在结果正确的前提下，运行时间越短越好
2、对于一些数据量较大的题目，需要尽力优化程序的运行时间，否则会因为超时而无法通过测试点不超过内存等资源限制
1、计算机的内存是有限的，所以使用过多的内存也是不行的
2、竞赛通常也会额外限制内存，因此需注意不要超出内存限制
时间复杂度
定义
1、一个语句的频度是指该语句在算法中被重复执行的次数
2、算法中所有语句的频度之和记为 $T(n)$，它是该算法问题规模 $n$ 的函数，时间复杂度主要分析 $T(n)$ 的数量级
3、算法中基本运算的频度(即最深层循环内的语句的频度)与 $T(n)$ 同数量级，因此通常采用算法中基本运算的频度 $f(n)$ 来分析算法的时间复杂度
4、因此算法的时间复杂度记为 $T(n) = O(f(n))$
5、含义上简单概括为算法的执行时间与输入值(问题规模)之间的关系分类
1、最坏时间复杂度：指在最坏情况下，算法的时间复杂度
2、平均时间复杂度：指所有可能输入实例在等概率出现的情况下，算法的期望运行时间
3、最好时间复杂度：指在最好情况下，算法的时间复杂度规则
1、加法规则：$T(n) = T_1(n) + T_2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))$ ；多项相加，只保留最高阶的项，且系数变为 $1$ (如 $O(n^2) + O(n^3) = O(n^3)$)
2、乘法规则：$T(n) = T_1(n) \times T_2(n) = O(f(n)) \times O(g(n)) = O(f(n) \times g(n))$ ；多项相乘，都保留
3、常见的渐进时间复杂度：$O(1) \lt O(\log_2 n) \lt O(n) \lt O(n\log_2 n) \lt O(n^2) \lt O(n^3) \lt O(2^n) \lt O(n!) \lt O(n^n)$ ；口诀：常对线幂指阶含义理解
1、$O(1)$ 是最低的时间复杂度，也就是耗时与输入数据大小无关，无论 $n$ 为几，运行步骤都是一样的
2、$O(\log_2 n)$，当数据增大 $n$ 倍时，耗时增大 $\log_2 n$ 倍。如数据增大 $256$ 倍，耗时只增加 $8$ 倍，如二分查找算法
3、$O(n)$，就代表数据量增大几倍，耗时也增大几倍
4、以此类推例题 1
程序
void fun(int n) { int i = 1; while (i <= n) i = i * 2; }解题步骤
找出基本运算：
i = i * 2设出执行时间：
t分析关系
t i 1 2 2 4 3 8 t $2^t$ 因为
while()执行 $i \leq n$ 次，即执行 $2^t \leq n$ 次，$t \leq \log_2 n$，$T(n) = O(\log_2 n)$
例题 2
程序
int x = 2; while (x < n / 2) x = 2 * x;解题步骤
找出基本运算：
x = 2 * x设出执行时间：
t分析关系
t x 1 4 2 8 3 16 t $2^{t+1}$ 因为
while()执行 $x \leq \frac{n}{2}$ 次，即执行 $2^{t+1} \leq \frac{n}{2}$ 次，$t+1 \leq \log_2 \frac{n}{2}$，$t \leq \log_2 n - 2$，根据加法规则 $T(n) = O(\log_2 n)$
例题 3
程序
int fact(int n) { if (n <= 1) return 1; return n * fact(n - 1); }解题步骤
if()为递归出口，始终执行一次，即为常数级 $O(1)$调用递归的
return中，$n$ 始终执行同样的乘法操作，所以为 $O(1)$；由于问题规模 $n$ 的函数与 $T(n)$ 挂钩，因此当问题规模变为 $n-1$ 时，则应为 $T(n-1)$此时分类讨论：当 $n \leq 1$ 时，$T(n) = O(1)$ ；当 $n \gt 1$ 时，$T(n) = O(1) + T(n-1)$
讨论 $n \gt 1$ 的时候，假设 $n$ 无限大。$T(n) = O(1) + T(n-1)$ ；此时 $T(n-1)$ 继续调用，$T(n) = O(1) + O(1) + T(n-2) = 2O(1) + T(n-2) $ ；再次调用，$T(n) = 3O(1) + T(n-3)$
此时出现规律，假设 $O(1)$ 前面的系数为 $i$，则 $T(n) = iO(1) + T(n-i)$ ；我们的目的是要消去 $T(n-i)$ 这项，所以要将它化为 $T(1)$ ，即令 $i = n - 1$ ，此时 $原式 = (n-1)O(1) + T(1)$
得出 $T(n) = (n-1)O(1) + T(1)$ ，常数级都可以忽略不计，根据加法规则，$(n-1)$ 的 $-1$ 也可以去除，所以最终 $T(n) = O(n)$
例题 4
程序
int count = 0; for (int k = 1; k <= n; k *= 2) for (int j = 1; j <= n; j++) count++;解题步骤
找出基本运算：
count++设出执行时间：
t易得内层循环次数为 n，设外层循环次数为 q
分析关系
q k 1 2 2 4 3 8 q $2^q$ 因为 $k \leq n$ ，所以 $2^q \leq n$ ，$q \leq \log_2 n$
外层循环循环一次，内层循环循环 $n$ 次，那么外层 $\log_2 n$ 次，内层则应为 $n\log_2 n$ 次
所以最终 $T(n) = O(n\log_2 n)$
例题 5
程序
int func(int n) { int i = 0, sum = 0; while (sum < n) sum += ++i; return i; }解题步骤
找出基本运算：
sum += ++i设出执行时间：
t分析关系
t sum 1 0+1 2 1+2 3 1+2+3 4 1+2+3+4 t 1+2+3+…+t 因为 $sum \lt n$ ，所以 $1 + 2 + 3 + \ldots +t \lt n$ ，等差数列 $\frac{t(t+1)}{2} \lt n$ ，化为 $t(t+1) \lt 2n$ ，可以忽略常数项，即 $t^2 < n$，则 $t < \sqrt{n}$
因此最终 $T(n) = O(t^{\frac{1}{2}})$
例题 6
程序
for (int i = n - 1; i > 1; i--) for (int j = 1; j < i; j++) if (a[j] > a[j + 1]) // (省略代码)a[j]与a[j+1]对调解题步骤
找出基本运算：
a[j]与a[j+1]对调设出执行时间：
t易得外层循环次数为 n，设内层循环次数为 q
分析关系
i q t n-1 n-1 (n-1)*(n-1) n-2 n-2 (n-2)*(n-2) n-3 n-3 (n-3)*(n-3) 易得 $T(n) = O(n^2)$
例题 7
程序
int x = 0; while (n >= (x + 1) * (x + 1)) x = x + 1;解题步骤
找出基本运算：
x = x + 1设出执行时间：
t分析关系
t x 1 1 2 2 3 3 t t 因为 $n \geq (x + 1) * (x + 1)$ ，即 $n \geq {(t+1)}^2$
所以 $t+1 \leq \sqrt{n}$，即 $t \leq n^{\frac{1}{2}} - 1$
根据加法规则，$T(n) = O(n^{\frac{1}{2}})$
空间复杂度
定义
1、与时间复杂度类似，类比时间复杂度指算法的运行时间与输入值(问题规模)之间的关系
2、由此空间复杂度便可简单概述为算法的存储空间与输入值(问题规模)之间的关系
3、算法的空间复杂度记为 $S(n) = O(f(n))$例题 1
程序
int sum(int n) { int value = 0; int ii = 1; while (ii <= n) { value = value + ii; ii++; } return value; }解题步骤
对于该程序而言，无论 $n$ 是多少，都只声明
value、ii两个变量因此 $n$ 对于空间没有影响，$S(n) = O(1)$
例题 2
程序
int sum(int n) { int value = 0; int ii[n]; // ... }解题步骤
如果 int 所占空间为 4B，那么该程序所需空间为 $4+4n$
根据加法规则，$S(n) = O(n)$
该题目若改为
int ii[n][n];二维数组，则 $S(n) = O(n^2)$
例题 3
程序
int sum(int n) { if (n == 0) return 0; int ii, jj, kk; return n + sum(n - 1); }解题步骤
同样分类讨论，显然当 $n=0$ 时 $S(n) = O(1)$，接下来讨论 $n \gt 0$ 时的情况
与时间复杂度方法类似，得出该函数共递归执行 $n$ 次，每次创建一组新的变量，因此 $S(n) = O(n)$
注意如果没有
int ii,jj,kk;空间复杂度 $S(n)$ 仍为 $O(n)$ ，因为递归函数每次递归时，新一次函数调用的形参也需要新的空间
例题 4
程序
int sum(int n) { if (n == 0) return 0; int arr[n]; return n + sum(n - 1); }解题步骤
分析关系
n(向下递归的过程) arr 所需空间 5 5 4 4 3 3 2 2 1 1 可以得出 $arr$ 所需的平均空间与 $n$ 的关系为 $\frac{n}{2}$，而函数形参所需空间为 $n$，每次递归都声明一组 $arr$
因此 $S(n) = O(\frac{n}{2}) * O(n)$，根据乘法规则，$S(n) = O(n^2)$
例题 5
程序
int sum(int n) { if (n == 0) return 0; int value = n + sum(n-1); int arr[n]; return value; }解题步骤
注意该程序与例题 $4$ 的程序的区别，该程序的数组定义在递归之后
这意味着在递去的过程中，没有创建数组，在归来的过程中创建。因此在递去过程中其他变量的复杂度为 $O(n)$，在归来过程中，创建完数组后函数就结束释放内存了，并不会继续占用空间，所以 $arr$ 最大占用空间也为 $n$
因此最终 $S(n) = O(n) + O(n) = O(n)$
如果较为紧急，建议添加微信或QQ，并注明来意
评论系统可能加载较慢，请耐心等待或刷新重试