python - 用递归计算大 O 符号

Question

我试图理解 Big O Notation 最坏情况下的运行时。但是我还是不太明白。

这是我最近写的一些代码:

def g(n):
    if n==0:
        return 1
    elif n==1:
        return 2
    else:
        n_div=n//2
        n_mod=n%2
        return g(n_div)*g(n_mod)

所以我希望我至少是对的:

def g(n):
    if n==0:
        return 1

和:

elif n==1:
    return 2

复杂度为 O(1)，所以恒定。

但是 else 部分呢。

它是 O(n) 是因为它取决于我选择的 n 吗？

谁能解释一下 else 部分的 Big O 复杂性是什么？

Answer 1

嗯，您已经注意到您可以将函数分成 3 个单独的情况，并且已经确定前 2 个是 O(1)。第三个稍微有点棘手，但您也可以将其分为两部分。

递归显然发生在:

g(n//2)*g(n%2)

我们可以立即看到 n%2 将评估为 0 或 1，这将再次解决前两种情况之一，因此我们可以忽略它。留给我们 g(n//2)。通过将其重写为打印循环并检查输出，您会注意到一些事情:

>>> n = 37
>>> while n > 1:
...     n //= 2
...     print(n)
...
18
9
4
2
1

如您所见，项每次都减少一半，递归中也会出现同样的情况。这是对数。

因此，此函数的最坏情况是 O(logn)。

您可以通过查看 this question 了解更多有关 logn 在 Big-O 表示法中的实际含义的信息.