algorithm - 算法时间复杂度总是 O(1) 优于 O(n)？

Question

我想问一下，如果我有一个需要 O(100) ---->O(1) 时间复杂度的算法，并且我有一个针对同一问题的算法，需要 O(n)来解决，但如果我知道它的最大值是 50 那么我可以决定它的最坏情况是 O(50) 所以在这样的情况下仍然 O(1) 算法或第二个 O(n) 算法是最好的选择？那么如果是第二个，我们总能说 O(1) 比 O(n) 更好吗？

Answer 1

当然，不是；并非总是。 大O只是一种渐近行为，这就是为什么

O(1) == O(0.001) == O(50) == O(100) == O(C) # where C is any positive constant

同样适用于O(n)

O(n) == O(0.001n) == O(100n) == O(C * n)    # where C is any positive constant

使用时序对两种算法进行成像

t1 = 1e100 (seconds) = O(1)
t2 = n     (seconds) = O(n)

对于无限 n (渐近行为)第一个算法比第二个算法更好，但对于所有现实世界的情况(小n)t2是优选的。即使缩放也不够:

t1 = 1000               (seconds)
t2 = 100 * n            (seconds)
t3 = n + 1e100 * log(n) (seconds)

算法 3 具有更好的缩放比例( 1 与 100 : n 与 100 * n )，但 1e100 * log(n)术语使得在现实世界的情况下不可能完成。

所以代替 O一般情况下，您应该比较函数:

t1 = 100 (seconds)
t2 = n   (seconds)

这里如果 n <= 50然后t2是一个更好的选择(对于 n > 1000 我们有一个完全相反的选择)