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

谢谢。

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在这里只是一个占位符}