2022年9月学习记录 - 时间复杂度题目训练

早在今年四月份的时候我就已经学习过时间复杂度了,但当时只是了解了以下，知道了这是什么东西，现在在做题时发现其实根本不会做题，所以现在来还债了。

我的学习资料

CSDN：王道数据结构选择题汇总

BiliBili：时间复杂度之2023王道课后题 (注：你完全可以在了解定义后看这个视频来学习时间复杂度)

(B站上找了一圈，发现这个视频时讲得最好的，除了声音有点小外没有其他缺点)

规则

加法规则：

$$T(n)=T_{1}(n)+T_{2}(n)=O(f(n))+O(g(n))=O(max( f(n),g(n) ) )$$

乘法规则：

$$T(n)=T_{1}(n)×T_{2}(n)=O(f(n))×O(g(n))=O(f(n)×g(n))$$

常用级数

收敛级数：

$$T(n) = 1+\frac{1}{2^2}+\frac{1}{3^2}+...+\frac{1}{n^2} < 1 +\frac{1}{2^2}+\frac{1}{3^2}+... = \frac{π^2}{6} = O(1)$$

调和级数：

$$T(n) = 1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n} = O(logn)$$

对数级数：

$$T(n) = log1 + log2 + log3 +...+logn = O(nlogn)$$

算术级数：

$$T(n) = 1 + 2 + ... + n = \frac{n(n+1)}{2} = O(n^2)$$

幂方级数：

$$T(n) = 1^2+2^2+3^2+...+n^2 = \sum_{k=0}^{n}k^2≈\int_{0}^{n}x^{2}dx=\frac{1}{3}n^{3}=O(n^{3})$$

几何级数：

$$T_{2}(n) = 1+ 2 + 4+ 8+...+2^n =\sum_{k=0}^{n}2^k = 2^{n+1}-1 =O(2^{n+1})=O(2^n)$$

迭代程序

迭代程序通常使用 while 循环或 for 循环表示，两者可以等价互换，而 for 循环便于计算时间复杂度，所以遇到 while 循环时统一转换为 for 循环以计算。

递归程序

递归方程： 递归关系简单的方程，可借助递推关系归纳出 T(n)与T(n – 1)等的关系，不断用递推方程的右部替换左部，直至 T(1)