c++ - 我如何直观地证明这段代码的时间复杂度

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

凭直觉来分析，我们假设数组中的所有数字都= k。这意味着我们可以在 return searchNumOccurrence(V, k, start, mid - 1) 中一次又一次地进行递归。假设我的开始是 0，结束是 N，这将执行 Log(N) 次。左边部分相同，答案是 *(2*Log(n))) = Log(n)。

然而，这个问题的答案在 O(N) 中。虽然理论上的证明是可以的，但我希望在 O(N) 中直观地真正理解它是如何实现的。

谢谢

Answer 1

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

另一种查看方式:查看函数调用树。这将是一棵二叉树(与二叉搜索不同，“树”是线性的)。这棵树的深度是O(log n)，而每一层的节点数是O(2^i)，其中i 是嵌套级别。所以最深嵌套层的节点数是O(2^log(n))，即O(n)。