O的运行时间复杂度(n/2) [英] Running Time Complexity of O (n / 2)

问题描述

我曾经了解这一点，但现在已经不复存在了.可以说我有一个算法，该算法将在数组中间返回数字.

I once understood this but not anymore. Lets say I have an algorithm that will return the number in the middle of an array.

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

最糟糕的情况永远是O(n/2)对吗?没有比这更糟的情况了.但是我们怎么得出结论是O(n)呢?

The worst case of this will always be O (n / 2) right? There is no worse case than this. But how come we just conclude that it is O(n) ?

推荐答案

大O时间复杂度与测量算法所需的实际时间无关，而是指定了时间复杂度所依赖的变量以及它们之间的何种关系.在这些变量和时间复杂度(即线性，多项式，指数等)之间.

Big O time complexity is not about measuring the actual time an algorithm will take, it instead specifies what variables the time complexity is dependent on and what kind of relationship there is between those variables and the time complexity (ie linear, polynomial, exponential, etc).

因为常量不会影响函数的类型，而时间复杂度是因为它们不会更改Big O值.

Because constants do not effect the type of function the time complexity is they do not change the Big O value.

请注意，在这种情况下，如果编译器足够聪明，可以注意到循环的所有迭代均已停止，但一个循环，则您编写的代码实际上可能会以恒定的时间编译为某种东西.

Note in your case the code you wrote may actually compile to something with constant time if the compiler is smart enough to note all iterations of the loop are dead but one.

这篇关于O的运行时间复杂度(n/2)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！