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

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)。

Answer 2

假设数组A只包含数字42，重复1000次。那么调用CCD_ 8将返回值1000。导致数字1000的每一个增量都来自最后一行中的"+1"的一次执行。因此，该行必须被执行1000=N次。

然而，如果数组包含不同的数字，则算法的作用类似于二进制搜索，并取O（log N）。