3

我只是不确定...

如果您的代码可以在以下任一复杂性中执行:

  1. 一个 O(n) 的序列,例如:两个 O(n) 的序列
  2. O(n²)

首选版本是可以在线性时间内执行的版本。是否有一段时间 O(n) 的序列会太多而 O(n²) 会是首选?换句话说,对于任何常数 C,陈述 C x O(n) < O(n²) 是否总是正确的?

为什么或者为什么不?有哪些因素会影响条件以便选择 O(n²) 复杂度会更好?

4

4 回答 4

9

我认为这里有两个问题;首先是符号表示的内容,其次是您在实际程序中实际测量的内容

  1. 大 O 被定义为 n -> 无穷大的限制,因此就大 O 而言,无论任何有限常数如何,O(n) < O(n^2) 始终为真。

  2. 正如其他人指出的那样,真正的程序只处理一些有限的输入,所以很有可能为 n 选择一个足够小的值,使得 c*n > n^2 即 c > n,但是严格来说你不再对付大O

于 2010-05-05T09:32:57.963 回答
2

如果你的常数 C 大于你的 n 值,那么 O(n²) 算法会更好。

于 2010-05-05T09:18:37.713 回答
1

O 表示法中总是有一个隐含的常数,所以是的,有可能对于足够小的 n,O(n^2) 可能比 O(n) 快。如果 O(n) 的常数远小于 O(n^2) 的常数,就会发生这种情况。

于 2010-05-05T09:19:53.227 回答
0

C x O(n) < O(n²) 并不总是正确的,在 n 中有一个点可以反转条件。

当 C 较大且 n 较小时,则 C x O(n) > O(n²)。但是,C 始终是恒定的,因此当 n 扩展到一个很大的数字时,C x O(n) < O(n²)。

因此,当 n 很大时,O(n) 总是优于 O(n²)。

于 2010-05-05T09:21:47.863 回答