complexity-theory - 线性复杂度和二次复杂度

Question

我只是不确定...

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

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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