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

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 个函数调用(有些返回 0，但它们不会产生新的调用)。因此，最坏的时间复杂度是O(N)。