首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

算法设计关于递归方程T(n)=aT(nb)+f(n)之通用解法

算法设计关于递归方程T(n)=aT(n/b)+f(n)之通用解法 在算法设计中经常需要通过递归方程估计算法的时间复杂度T(n),本文针对形如T(n)=aT(n/b)+f(n)的递归方程进行讨论,以期望找出通用的递归方程的求解方式...设a≥1,b>1为常数,f(n)为函数,T(n)=aT(n/b)+f(n)为非负数,令x=logba: 1. f(n)=o(nx-e),e>0,那么T(n)=O(nx)。...3. f(n)=w(nx+e),e>0且对于某个常数c<1和所有充分大的n有af(n/b)≤cf(n),那么T(n)=O(f(n))。 然而,Master定理并没有完全包括所有的f(n)的情况。...注意到条件1和3中的e总是大于0的,所以在条件12、条件2和3之间存在所谓的“间隙”,使得某些f(n)在该情况下不能使用该定理。...综上所述,可以得出以下结论:在针对形如T(n)=aT(n/b)+f(n)的递归方程求解方法里,使用递归树是一种比较可行的通用办法。

1.5K70

常见算法的时间复杂度 Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…

比如:Ο(1)、Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)、Ο(n3)…Ο(2n)、Ο(n!)等所代表的意思! 我在面试的时候,就发现有人连 O(1) 代表什么意思都搞不清楚!...关于时间复杂度,有一个公式:T (n) = Ο(f (n))。怎么解释这个公式呢?特别麻烦,我目前还没有想到比较简单的介绍方式。所以,我就先不解释它了。 所以,我们就先来看看 O(1) 是什么意思?...O(n^2) 就代表数据量增大 n 倍时,耗时增大 n 的平方倍,这是比线性更高的时间复杂度。比如冒泡排序,就是典型的 O(n^2) 的算法,对 n 个数排序,需要扫描 n × n 次。...常见的时间复杂度有:常数阶 O(1),对数阶 O(log2n),线性阶 O(n),线性对数阶 O(nlog2n),平方阶 O(n2),立方阶 O(n3),…,k 次方阶 O(nk),指数阶 O(2n)...常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)。 ? 上图是常见的算法时间复杂度举例。

7.8K21
领券