algorithm - 大哦 - O(n) vs O(n^2)

Question

我最近完成了两个数据结构类测试，我有一个与 O(n) vs O(n^2) 有关的问题错了两次。我想知道是否可以帮助我理解这个问题。问题是:

假设算法 A 的运行时间为 O(n^2)，算法 B 的运行时间为 O(n)。当 n=17 时，这两种算法的运行时间如何？

a) 当 n=17 时，我们不能说具体的运行时间

b) 算法 A 将比算法 B 运行得更快

c) 算法 A 将比算法 B 运行得慢得多

对于这两个测试，我根据以下内容回答了 C:https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions .根据提供的链接，我知道 B 没有意义。现在我开始认为它是 A。我猜它是 A，因为 n 很小。如果是这种情况，我想知道什么时候 n 足够大以至于 C 成立。

Answer 1

这里其实有两个问题。

第一个就是你提到的那个。增长阶数是渐近的。他们只是说存在一些 n₀，对于任何 n > n₀，函数是以某种方式受到限制。他们对 n 的具体值只字不提，只说“足够大”的值。

第二个问题(您没有提到)是O 是just an upper bound (as opposed to Θ) ，因此即使 n 足够大，您也无法比较两者。因此，如果 A = √n 且 B = n，则显然 B 比 A 增长得更快。然而，A 和 B 仍然符合问题，因为 √ n = O(n²) 和 n = O(n)。