渐进符号

渐进符号介绍

• $O()$O()，$f(n)=O(g(n))$f(n)=O(g(n))表示存在适当的常数$c>0,n_0>0$c>0,n0​>0，使得$f(n)\le cg(n)$f(n)≤cg(n)，比如$n^2=O(n^3)$n2=O(n3)
• $\Omega()$Ω()，$\Omega(g(n))=f(n)$Ω(g(n))=f(n)表示存在适当的常数$c>0,n_0>0$c>0,n0​>0，使得$0 \le cg(n) \le f(n)$0≤cg(n)≤f(n)，比如$\sqrt{n}=\Omega(lgn)$n​=Ω(lgn)
• $\Theta()=O(g(n)) \cap \Omega(g(n))$Θ()=O(g(n))∩Ω(g(n))，忽略常数项的相等，比如$n^2+O(n) =\Theta(n^2)$n2+O(n)=Θ(n2)
• $o()$o()，$f(n)=o(g(n))$f(n)=o(g(n))表示对于任意$c$c存在适当的常数$n_0&gt;0$n0​>0，使得$f(n)&lt;(n)$f(n)<(n)，比如$2n^2=o(n^3)$2n2=o(n3)，$\frac{n^2}{2}=\Theta(n^2)$2n2​=Θ(n2)不是$o、\omega$o、ω关系，因为它是严格的$n^2$n2
• $\omega()$ω()，$\omega(g(n))=f(n)$ω(g(n))=f(n)表示对于任意$c$c存在适当的常数$n_0&gt;0$n0​>0，使得$0 &lt; cg(n) &lt; f(n)$0<cg(n)<f(n)，比如$\sqrt{n}=\omega(lgn)$n​=ω(lgn)

解递归

代换法(Substitution method)

介绍

• 猜解的形式
• 按照数学归纳法验证是否正确
• 设法找出解

举例

比如，$T(n) = 4T(n/2) + n$T(n)=4T(n/2)+n，猜想$T(n)=O(n^3)$T(n)=O(n3)，则在$k&lt;n$k<n下$T(k) \le ck^3$T(k)≤ck3，利用数据归纳证明$T(n) \le cn^3$T(n)≤cn3。

下面尝试证明更紧的上界$O(n^2)$O(n2)

所以不能小于等于$n^2$n2，但从直观上看$n^2$n2的形式应该成立，所以考虑

递归树(Recursion-tree method)

介绍

• 执行成本高
• 可以辅助代换法第一步猜想解
• 有点不可靠，中间过程迭代容易有点问题

举例

$T(n) = T(n/4) + T(n/2) + n^2$T(n)=T(n/4)+T(n/2)+n2，
用树的形式展开递归

主方法(master method)

介绍

只能用于特定的递归式$T(n) = aT(n/b) + f(n),a\ge 1,b&gt;1,f$T(n)=aT(n/b)+f(n),a≥1,b>1,f函数渐进趋正（对足够大的n,$f(n)$f(n)是正的）。
三种常见的情况：

举例

推导