コードの最悪の時間複雑度

Question

次のコードの最悪の時間複雑さはなぜO（N）ですか？

/* 
* 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

最悪の場合はどうなりますか？最悪の場合は、すべての要素が同じで、kに等しいことになります。それで少なくともすべての要素を読む必要があります。それはNです。ほとんどの関数呼び出しは出力を1増加させるので、約N関数呼び出しがあります（いくつかは0を返しますが、新しい呼び出しを生成しません）。したがって、最悪の時間の複雑さはO(N)です。

Answer 2

はい、アレイ内のすべての番号がkに等しい場合、最悪の場合には、この最悪の場合には、漸化式がなければならない：これはO(n)に変換

T(n) = 2*T(n/2) 

。