python - 这个函数的大O是怎样的O(n^3)？

Question

我被这个大 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)

Answer 1

您的函数有两个嵌套的 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) .