计算伪代码的时间复杂度

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减半。

关键是你的变量如何接近循环边界。如果它按常数步长递增/递减。那么它是线性的。但是如果涉及到其他操作，您需要考虑到这一点。