计算伪代码的时间复杂度

Question

我正在尝试分析算法的时间复杂度。

下面的算法是为了只检查数组的一部分，所以如果它没有多大意义也不用担心。

我对计算循环的时间复杂度很困惑，请看我的评论。

def search(key,arr) 
   N = arr.length                    C1
   for 0 <= i < ceiling(N/2)         C2*N+C3 - ceiling can be considered a constant. 
      if(arr[i] == key):             C4*N -- Assuming this because its inside the loop?
      return 2*i                     C5*N -- N because of the loop?
   return "Not found"                C6

这是否意味着我们有：

T(N) = (C2+C4+C5)N + (C1+C3+C6)

T(N) = C7*N + (C8)

T(N) = N??

循环内的所有内容总是 *N?

提前致谢！

Answer 1

你的计算是正确的。这是一个 O(n) 算法。

但你不能说循环内的所有内容总是 N 次。考虑以下示例：

for i == N; i >= 0; i /= 2:
  ... do some constant stuff

这显然是 N 的对数，因为我们在每次迭代中减半 i。

关键是你的变量如何接近循环边界。如果它 increments/decrements 通过不断的步骤。然后是线性的。但如果涉及到其他操作，则需要考虑。