代码的最坏时间复杂度

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);
}

- fidgetyphi

Answer 1

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

- lnyng

Answer 2

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

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

这可以翻译成O(n)。

- Abhishek Bansal

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)

- Rawr