作者：非妃是公主
专栏：《算法》
个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩
专栏系列文章
复习重点
算法复杂度分析——主方法
T
(
n
)
=
a
T
(
n
b
)
+
f
(
n
)
T(n)=aT(\frac{n}{b})+f(n)
T(n)=aT(bn)+f(n)
- 其中
a≥1和b>1是常数，f(n)是渐进函数 。 - 上述递归式描述的是这样一种算法的运行时间：
- 它将规模为
n的问题分解为a个子问题 每个子问题规模为n
b
\frac{n}{b}
bn ，其中a和b都是正常数。 - a 个子问题递归地进行求解，每个花费时间 T(n/b) 。
- 函数 f(n) 包含了问题分解和子问题解合并的代价 。
- 其中
n
b
\frac{n}{b}
bn 指n
b
\frac{n}{b}
bn 的上取整或者是下取整，对结果不会造成影响。
- 它将规模为
例题1：
例题2：
例题3：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/130517.html
