代码之家 › 专栏 › 技术社区 › user2303325

通过证明递归是Omega(nlogn)来归纳证明递归不是O(n)

induction proof time-complexity big-o math

user2303325 · 技术社区 · 9 年前

注意:这与家庭作业有关。

我正试图证明这一点 T(n/3) + T(2n/3) + n >= cn , for all c > 0 .

当我尝试这样做时,基本案例失败了 (T(1) = 1 >= cn, for all c > 0 ,不是真的)。为了解决这个问题,我想证明这个问题有一个比 O(n) 。这是否构成正确的证明?

1 回复 | 直到 9 年前

templatetypedef 9 年前

作为提示,尝试添加更多术语。假设函数满足

T(n)≥ k _1. n对数n+k _2. n+k _3.

现在,当你插入n=1时,可以通过设置k使右手边为非零 _2. 和k _3. 适当地。这类技术通常用于对上限和下限函数进行归纳,因为这些低阶项与big-O表示法无关,并且可以优雅地处理较小的情况。

推荐文章

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

Wadu Hek · 查找列表中唯一的重复项

2 年前

Crawford Patten · 如何获得整数列表的四分位数

2 年前

MoonGoose · 如何在python中围绕特殊字符创建空间?

2 年前

diamondog · 在python中获取程序上奇怪的额外数字以倒计时

2 年前

taha khamis · 在一个数字中组合元素的省道

3 年前

Soup · 比O(n)更快地找到阶乘n模m

3 年前

Terry5 · 为什么呢。lshift(1,40)是256,而不是109951162776

3 年前

BigO · 单词积分游戏不断增加数字[关闭]

3 年前