O(n/2)的运行时间复杂度是什么？

Question

曾经我理解过这个算法，但现在不再理解了。假设我有一个算法，可以返回数组中间的数字。

for (int i = 0; i < nums.length; i++) {
  if (i == nums.length / 2) return nums[i];
}

这种情况的最坏时间复杂度始终为O(n/2)，对吗？没有比这更糟糕的情况了。但是我们为什么会得出它的时间复杂度是O(n)的结论呢？

- Zanko

---

为了进行 O(...) 分析，常数并不重要。重要的是随着元素数量的增加，时间如何增长，而不是时间的绝对值。 - Mark Ransom

“2”是某个常数因子，因此“O(n/2)”可以简化为“O(n)”。换句话说，查看一半元素的复杂度不比查看所有元素更差。 - OneCricketeer

让我困扰的是O(n/2)被简化为O(n)。如果代码写成if (i == nums.length / 999999999) return nums[i];而不是if (i == nums.length / 2) return nums[i];，那么它总是会返回第一个元素。所以(O(n / 99999999)技术上是O(1)吗？ - Zanko

@Zanko 不，O(n / 99999999) 仍然是 O(n)，因为 n 没有限制。如果 n=9999999999999999999999999，你可以看到它仍然比 n=1 花费更长的时间。 - Mark Ransom

Answer 1

大O时间复杂度并不是用来测量算法实际执行时间的，它指定了时间复杂度所依赖的变量以及这些变量与时间复杂度之间的关系（例如线性、多项式、指数等）。

由于常数不影响时间复杂度函数的类型，它们不会改变大O值。

请注意，在您的情况下，您编写的代码可能会被编译成具有恒定时间的内容，如果编译器足够聪明以注意到循环的所有迭代都死亡但一个。

- Vality

---

你好，如果我有另一个算法，它循环整个数组而不是一半，那该怎么办呢？所以它们都是O(n)。但是当人们想知道哪个更快时，他们会说速度相同，但实际上只循环一半的那个是两倍快！ - Zanko

@Zanko 这是真的，但是大O符号并不适用于这个任务。我不知道是否有其他符号可以准确描述你所寻找的内容（并不代表不存在，只是我不知道）。我建议使用一些词语来描述一个比另一个快两倍。 - Vality

@Zanko 知道哪个算法更快 并不是 Big-O 有用的地方 - 它是用于预测算法对不同大小输入的反应！发现在小的 n 上更快的具有更高 O() 的算法并不罕见。 - Mark Ransom

如果你想保持常数不变，可以使用波浪符表示法。然而，这在实际中并不常见，虽然是由Sedgewick和Wayne首创。 - njlarsson