以下算法的递归关系是什么？

Question

下面的递归关系是T(n) = T(n-1) + 2 + T(n+1)吗？
我只计算中间变量赋值和最后一行，因为所有 if 语句都排除了其他语句...这种方法正确吗？

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

Answer 1

@GAURANG VYAS 在评论中提到。递归关系是 T(n)=2*T(n/2) + O(1) 并且在 Theta(n) 中。 Binary Search 将在 O(log n) 及其递归关系 T(n)=T(n/2) + O(1)

由于您的方法 searchNumOccurrence() 查找给定 k 的所有出现，它可能会查看 V 中的所有元素。如果 V 中的所有元素都等于 k ​​的典型示例。