代码的最坏情况时间复杂度

Question

为什么下面代码的最坏时间复杂度是O(N)？

/* 
* V is sorted 
* V.size() = N
* The function is initially called as searchNumOccurrence(V, k, 0, N-1)
*/

int searchNumOccurrence(vector<int> &V, int k, int start, int end) {
  if (start > end) return 0;
  int mid = (start + end) / 2;
  if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end);
  if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1);
  return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end);
}

Answer 1

最坏的情况是什么？最坏的情况是所有元素都相同且等于 k。那么你至少要读取所有的元素，也就是N。由于大多数函数调用将输出增加 1，因此大约有 N 个函数调用（一些 returns 0，但它们不会产生新的调用）。因此，最差的时间复杂度是O(N).

Answer 2

是的，在最坏的情况下，如果数组中的所有数字都等于k，那么在这种最坏的情况下，递推关系应为：

T(n) = 2*T(n/2)

这转化为O(n)。

Answer 3

最后一个案例-

return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end);

是瓶颈步骤。假设数组中的所有值都相同，我们得到以下关系：

T(N) = 2 * T(N/2) + constant
= 4 * T(N/4) + constant ( 2 * constant = another constant ) 
= 8 * T(N/8) + constant 
.....
= N * T(N/N) + constant 
= N + constant 
= O(N)

代码的最坏情况时间复杂度

Worst case time complexity for the code

algorithm

big-o

vector

time-complexity