我试图理解 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 复杂性是什么?
最佳答案
嗯,您已经注意到您可以将函数分成 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 表示法中的实际含义的信息.
关于python - 用递归计算大 O 符号,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47404869/