大三落汤狗の算法笔记 (持续更新)

1. 算法复杂度分析

简便：复杂度取阶数最高项，去系数。如：O(3n²+2n+1)=O(n²)
O()低阶/o()，Ω()高阶/w()，θ()同阶
阶关系成立：自反OΩθ/对称θ/传递OoΩwθ
O(f)+O(g)=O(max(f,g))
O(f)+O(O(f))=O(f)

O(递归)

迭代法：

n次计算，每次O(单次)求和
eg: 求n!

1. 求退出条件：T(1)=1
2. 求递推公式：T(n) = T(n-1)+1
3. 展开递推公式:= T(n) = T(n-1)+1 = T(n-2)+1+1 = ... = T(1)+n-1 = O(n)

Master法：