运行时间复杂度为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) 呢？

Answer 1

Big O 时间复杂度并不是衡量算法实际花费的时间，而是指定时间复杂度取决于哪些变量以及这些变量与时间复杂度之间存在什么样的关系（即线性、多项式、指数、等）。

因为常量不会影响函数的类型，所以时间复杂度是它们不会改变 Big O 值。

请注意，在您的情况下，如果编译器足够聪明，可以注意到循环的所有迭代都已死，那么您编写的代码实际上可能会编译为具有恒定时间的代码。