algorithm - 费用。算法分析。中的算法

Question

可以说 O(n²) 算法的成本总是小于 O(n) 的成本。评论陈述的真实性：

标签： algorithm

Answer 1

不。说一个算法是 O(n²) 意味着至少有一种情况，该算法需要二次运算才能完成。

在 O(n) 算法中，最坏情况将是线性的，因此对于足够大的输入，O(n²) 算法的最坏情况总是比 O(n) 算法需要更多的操作。

O(n) = k * n + a
O(n²) = k2 * n² + k1 * n + b

so we wanna prove that there is a case that O(n) < O(n²)

k * n + a < k2 * n² + k1 * n + b
(k - k1) * n + (a - b) < k2 * n²
(k - k1) / k2 + (a - b) / (k2 * n) < n

我们可以看到，随着n增长，左侧的常数将保持不变或减少，因此会有一个 O(n) < O(n²) 的点。