以下搜索算法的时间复杂度是多少？

Question

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

这段代码的时间复杂度是多少？我觉得它的 O(logN) 但正确答案是 O(N)。谁能解释清楚为什么？

Answer 1

它是 O(N) 因为如果你总是选择这个“分支”（数组包含 N 个值为 k 的元素）

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

你必须做2次调用，你可以把它想象成一个完整的树遍历，也就是O(N)

以下搜索算法的时间复杂度是多少？

What is the time complexity of the following search algorithm?

c++

algorithm

search

binary-search

time-complexity