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

大O复杂性

big-o python-3.x

user6217340 · 技术社区 · 7 年前

我试图理解Big O,并认为通过一个简单的程序进行操作可能会有所帮助。

def sum(n):
    k = 0
    j = 0
    while k < n:
        k = k + 1
    while j < n:
        j = j + 1
        k = k + j
    return k

k和j最初被分配值0,该值计为2次分配,第一个while循环执行1次分配n次,第二个while执行2次分配n次。所以表达式是2+n+2n。

由于上述表达式中的前两项(2和n)是常数,因此与第三项相比,它们将变得无关紧要,第三项随着n的增长将n乘以2。所以代码的大O就是O(2n)。

我的逻辑和答案正确吗?提前感谢

1 回复 | 直到 7 年前

Olivier Melançon iacob 7 年前

你的回答是正确的,尽管我们没有说 O(2n) 但是相反

什么 O(n) 也就是说,最坏情况下算法的时间复杂度最多呈线性增加,也就是说最后受窗体的某个函数约束 a * n 哪里一是一个常数。实际常数与big-O表示法无关。

我说,更专业一点最后因为我们讨论的是我们称之为算法的极限行为,所以您可以认为它只描述了非常大的输入的行为。

通过you算法中的示例,如 n 我们越来越不关心分配 k = 0 和 j = 0 ,它们变得微不足道。

总之,big-O符号旨在描述 运行时间增长的速度 ,而不是准确描述运行时是什么。

推荐文章

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

3 年前

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

7 年前

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

7 年前

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

7 年前

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

7 年前

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

7 年前

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

7 年前

user3487554 · 时间复杂性组合

7 年前

user6217340 · 大O复杂性

7 年前

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

7 年前