线性复杂度和二次复杂度

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.