大 O 表示法中有 O(n/2) 这样的东西吗？

Question

我有一个数组，每次都增加两个。由于有一半的增量，我会说 O(n/2) 还是 O(n) 因为它是线性的？

Answer 1

只是O(n)。Big-O 不关心常数因素。（或者更确切地说，乘以任意有限因子已经是 big-O 定义的一部分，因此在其中指定另一个常数因子是多余的。）从技术上讲：

定义：f(x) = O(g(x))当x -> infinity且仅当存在一个实数M和正实数x0使得|f(x)| <= M * |g(x)|对于所有x > x0。

但是，如果您g(x)实际上是1/2 h(x)，那么您可以创建一个新的M'使得M = 2 M'，并以这种方式表达：|f(x)| <= 2M' * |1/2 h(x)| = M'|h(x)|- 即O(n)相当于O(n/2)。

换句话说：big-O 表示性能如何随着输入大小的变化而变化。如果您将数组加倍，您的时间就会加倍——无论是读取每个元素，还是每隔一个。

这也是将有限的数据大小大澳的危险之一：如果你知道你只有10000行和两种算法之间选择，它不一定是情况O(n)会比好O(n^2)-也许后者有每个周期的时间非常快，而前者一次研究每个元素几分钟。唯一与 big-O 相关的地方是缩放度量。