如何直观地证明这段代码的时间复杂性

Question

我有一段代码如下：

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

考虑相同数字的最坏情况：您的算法将读取所有输入数字：与之比较时的中间元素，然后是前半部分，然后是后半部分。要检查一个元素，它需要O(1)，所以要检查n元素，它需要O(n)。

另一种看它的方法：看函数调用的树。这将是一个二叉树（不像二分搜索，其中的“树”是线性的）。此树的深度为O(log n)，而每个级别的节点数为O(2^I)，其中I是嵌套级别。因此最深嵌套层的节点数为O(2^log(n))或O(n)。