为什么下面代码的最坏时间复杂度是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);
}
最佳答案
最坏的情况是什么?最坏的情况是所有元素都相同且等于 k
。那么你至少要读取所有的元素,也就是N
。由于大多数函数调用将输出增加 1,因此大约有 N
个函数调用(有些返回 0,但它们不会产生新的调用)。因此,最坏的时间复杂度是O(N)
。
关于algorithm - 代码的最坏情况时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39177163/