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

大θ示例

big-o

NoviceProgrammer123 · 技术社区 · 8 年前

我对这个问题有疑问。我知道,对于一个函数等于另一个函数的大θ,当n趋于无穷大时,f(n)/g(n)的极限必须等于一个非零常数。但我从来没有用求和来计算极限(更不用说两个求和,一个大于另一个)。有人能给我解释一下或给我指出正确的方向吗?谢谢

PROBLEM

1 回复 | 直到 8 年前

meowgoesthedog 8 年前

这些是 几何级数 . 有一个评估它们的标准公式:

所以问题变成了:

这就是错误像 3^n 指数增长速度超过 2^n ,因此它们不能具有相同的复杂性类别。

推荐文章

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

4 年前

Dazcii · 如何找到3个嵌套循环的复杂性

8 年前

Kodean · Java:循环字符串长度时间复杂性

8 年前

screeb · 依赖于收敛的算法的大O

8 年前

f1sh3r0 · 从图中确定渐近增长率

8 年前

shinwari_afg · 使用大Oh分析while(key<=N*N)循环的复杂性

8 年前

alekscooper1 · 这里是f(x)=O(g(x))还是反之亦然?

8 年前

user3487554 · 时间复杂性组合

8 年前

user6217340 · 大O复杂性

8 年前

Jawwad Rafiq · 对两个相关循环的复杂性感到困惑?

8 年前