我被这个大 O 表示法困住了,它应该是 O(n^3) 的。我的思维过程哪里出了问题?
我知道嵌套的 for 循环是 O(n^2) 并且 while 循环可能是 O(nlogn) 函数,因为 for 循环是 O(n) 函数并且 while 循环的值是乘以 2 使其变为 O(logn)。话虽这么说,答案据说是 O(n^3),我很困惑这是怎么来的,除非函数的递归部分与它有关?
def do_stuff2(n, x=1.23):
if n <= 0:
return 0
val = 1
for i in range(n//2):
for j in range(n//4):
x += 2*x + j/2 + i*1.2
while val <= n:
for i in range(n):
x += val**2 + i//2
val *= 2
x += do_stuff2(n - 1, x/2)
return x
我相信 x 不会影响大 o 表示法,因为它是一个常量,因为它不用于决定任何循环的循环次数。
同样,我预计函数的输出为 O(n^2),但实际输出为 O(n^3)
最佳答案
您的函数有两个嵌套的 for 循环,即 O(n^2)
:
for i in range(n//2):
for j in range(n//4):
x += 2*x + j/2 + i*1.2
但最重要的是,您的 do_stuff2()
函数接受一个参数 n
并调用自身直到 n <= 0
,这意味着又一个 O(n)
.
关于python - 这个函数的大O是怎样的O(n^3)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56358621/