大O复杂度

Question

我试着理解“大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次，第一次which循环执行1次赋值n次，第2次执行2次赋值n次。表达式为2+n+ 2n。

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

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

Answer 1

你的答案是正确的，虽然我们不是说O(2n)，而是O(n)。

O(n)的意思是，最坏的情况下，你的算法的时间复杂度最多是线性增加的，也就是说，它最终受到形式a * n的某个函数的约束，其中a是某个常数。实际常量与大O表示法无关.

为了更专业一点，我最后说，因为我们说的是我们所说的算法的极限行为，你可以把它想象成只对非常大的输入描述这种行为。

例如，在您的算法中，随着n的增长，我们对分配k = 0和j = 0的关注越来越少，它们变得微不足道。

总之，大O符号的目的是描述运行时间增长的速度，而不是精确地描述运行时是什么。