Skip to main content

01D 复杂度分析

算法分析​

两个主要任务 = 正确性(不变性 * 单调性) + 复杂度

  • 迭代： 级数求和
  • 递归： 递归跟踪 + 递推方程 + 猜测验证

级数​

  • 算术级数： 与末项平方同阶 1 + 2 + ... + n = O(n^2)
  • 幂方级数： 比幂次方高出一阶 1^2 + 2^2 + ... n^2 = O(n^3)
  • 几何级数：与末项同阶 a^0 + a^1 _... + a^n = O(a^n)
  • 收敛级数: 1/3 + 1/7 + 1/8 + 1/15 + ... + 1/(n^2-1) = 1 = O(1)， 比如抛硬币，每次的概率小于1, 可能用到小于1的项。
  • 未必收敛但长度有限
    • 调和级数 h(n) = 1 + 1/2 + 1/3 ... + 1/n = Θ(logn)
    • 对数级数 log1 + log2 + ... + logn = log(n!) = Θ(nlogn)

循环​

i, j 两层循环对应算术级数， 即 O(n^2), 也可以想象为矩形面积。

非极端元素 + 起泡排序​

非极端元素 ， 任意取3个元素，中间值，O(1) 算法

起泡排序，任意一对相邻元素都是顺序或逆序的

正确性证明​

有穷性 <- 不变性 单调性 正确性

封底估算​

  • 原子弹当量
  • 地球直径 787 * 360/7.2 = 39350
  • 人口普查数据排序
    • 硬件提升 30年 -》20分;
    • 算法提升 30年 -》30秒

1天 = 10^5秒
1生 = 100 年 = 3 * 10^9 秒
三生三世 = 300年 = 10^10 秒