成本。算法分析。中的算法

Question

可以说，O(n²)算法的成本将始终小于O(n)的成本。评论这句话的真实性：

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²)。