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 值。

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