algorithm - Big-O 表示法和时间复杂度混淆

Question

我们的老师给了我们这个关于时间复杂度分析的小组作业。

一个算法需要 100 秒来处理 5000 条数据，如果需要 2400 秒来处理 400000 条数据，那么这个算法的时间复杂度近似值是多少？（大 O 表示法）

我们制作了这个 Python 脚本来近似大 O 符号。

import math
def O(n):
    return (n**(1/4))*(math.log(n, 2)**5)

print(O(400000)/O(5000)) # Prints 23.82907726248897 this is the best approximation we've got

此外，我们已经讨论了很远，关于其中一些符号，它们是否相同？

• O(2^n) 和 O(3^n)
• O(n^k) 和 O(n^(k+1))
• O(n^(1/2)) 和 O(n^(1/3))

先感谢您。

标签： algorithmtime-complexitybig-o

Answer 1

我认为您对小组作业的近似值已经足够了。干得好！但是人们很少以黑盒方式（计算时间和近似值）分析他们的程序，因为人们总是知道算法和实现。所以不要把作业看得太认真；）

正如您所提到的，以下符号对确实是不同的：

• O(2^n) 和 O(3^n)
• O(n^k) 和 O(n^(k+1))
• O(n^(1/2)) 和 O(n^(1/3))

每对符号之间都有不可忽略的间隙。