算法的复杂度与Master定理
需积分: 37 99 浏览量
2013-06-13
22:00:21
上传
评论
收藏 18KB DOCX 举报
算法的复杂度与 Master 定理
平时设计或者阅读一个算法的时候，必然会提到算法的复杂度（包
括时间复杂度和空间复杂度）。比如我们说一个二分查找算法的平
均时间复杂度为 O(log n)，快速排序可能是 O(n log n)。那这里的
O 是什么意思？这样的表达是否准确呢？
今天来复习一下与算法复杂度相关的知识：函数渐进阶，记号
O、Ω、θ 和 o；Master 定理。
先插一句，在算法复杂度分析中，log 通常表示以 2 为底的对数。
算法复杂度（算法复杂性）是用来衡量算法运行所需要的计算机资
源（时间、空间）的量。通常我们利用渐进性态来描述算法的复杂
度。
用 n 表示问题的规模，T(n)表示某个给定算法的复杂度。所谓渐进
性态就是令 n→∞时，T(n)中增长最快的那部分。严格的定义是：如
果存在 T˜(n)，当 n→∞时，有
T(n)−T˜(n)T(n)→0
就说 T˜(n)是 T(n)当 n→∞时的渐进性态。
比如 T(n) = 2 * n ^ 2 + n log n + 3，那么显然它的渐进性态是
2 * n ^ 2，因为当 n→∞时，后两项的增长速度要慢的多，可以忽
略掉。引入渐进性态是为了简化算法复杂度的表达式，只考虑其中
资源评论
