我只是不确定...
如果您的代码可以在以下任一复杂性中执行:
- 一个 O(n) 的序列,例如:两个 O(n) 的序列
- O(n²)
首选版本是可以在线性时间内执行的版本。是否有一段时间 O(n) 的序列会太多而 O(n²) 会是首选?换句话说,对于任何常数 C,陈述 C x O(n) < O(n²) 是否总是正确的?
为什么或者为什么不?有哪些因素会影响条件以便选择 O(n²) 复杂度会更好?
我只是不确定...
如果您的代码可以在以下任一复杂性中执行:
首选版本是可以在线性时间内执行的版本。是否有一段时间 O(n) 的序列会太多而 O(n²) 会是首选?换句话说,对于任何常数 C,陈述 C x O(n) < O(n²) 是否总是正确的?
为什么或者为什么不?有哪些因素会影响条件以便选择 O(n²) 复杂度会更好?
我认为这里有两个问题;首先是符号表示的内容,其次是您在实际程序中实际测量的内容
大 O 被定义为 n -> 无穷大的限制,因此就大 O 而言,无论任何有限常数如何,O(n) < O(n^2) 始终为真。
正如其他人指出的那样,真正的程序只处理一些有限的输入,所以很有可能为 n 选择一个足够小的值,使得 c*n > n^2 即 c > n,但是严格来说你不再对付大O
如果你的常数 C 大于你的 n 值,那么 O(n²) 算法会更好。
O 表示法中总是有一个隐含的常数,所以是的,有可能对于足够小的 n,O(n^2) 可能比 O(n) 快。如果 O(n) 的常数远小于 O(n^2) 的常数,就会发生这种情况。
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²)。