python - 具有嵌套循环的python中函数的时间复杂度

Question

为什么是 O(n^6)？而不是 O(n^9)？

def fa1(n):
    k = 0
    for i in range(1, (n ** 6) + 1) :
        for j in range(i * 3, (n ** 3) + 1):
            k += 1

谢谢。

标签： pythonpython-3.xtime-complexity

Answer 1

首先，根据大 O 表示法O(n^6)的定义，计算也是O(n^9)( n >= 0) 。后者只是一个较差的近似值。

其次，如果你像这样重写你的函数是微不足道的：

def fa1(n):
    k = 0
    for i in range(1, ((n ** 3) + 1)//3 + 1) :
        for j in range(i * 3, (n ** 3) + 1):
            k += 1

    for i in range(((n ** 3) + 1)//3 + 1, (n ** 6) + 1) :
        for j in range(i * 3, (n ** 3) + 1):
            k += 1

第二个循环总是i * 3 >= (n ** 3) + 1，因此内部循环被跳过，因为range是空的。因此，该函数等价于：

def fa1(n):
    k = 0
    for i in range(1, ((n ** 3) + 1)//3 + 1) :
        for j in range(i * 3, (n ** 3) + 1):
            k += 1

这显然是O(n^6)均匀的θ(n^6)（大 Theta）。

_{您可以k更直接地计算，但我想k += 1这里只是一个占位符。}