algorithm - アルゴリズムの時間計算量

Question

無限整数のソート済み配列でキーを見つけるアルゴリズムを作成しました。

 findKey(int k, int start, int end)
     int mid = (start + end)/2

     if (k < array[mid])
         findKey(k, start, mid)
     else if (k > array[mid])
         findKey(k, mid+1, end)
     else 
         return mid

このアルゴリズムの時間計算量を知りたいです。o(logn)ですか？私は本当に混乱しています、誰か説明できますか？また、ここに欠陥がある場合はお知らせください。前もって感謝します。

Answer 1

格納された値を持つ配列を用意しましょう

key=20 を見つけたいとします。パラメーター k=20、start=1、end = 8 で findkey(20,1,8) を呼び出します。

一連の関数呼び出し

Recurrence relation :

T(n)  = T(n/2)+c
 expanding…
          =T(n/2^2)+c+c
          =T(n/2^3)+c+c+c

Kth time expanding…

          = c+c+c+c+c . .. .. . .. . . .  .T(n/2^k)

Let at kth time array size become 1,
we assume it as a base condition for recurrence.
Thus , 
   n/2^k = 1
      n  = 2^k
Taking log both sides ..
    log n = k

 time complexity of recurrence..

   T(n) = c* log n 
        = O(log n) 

Answer 2

あなたが作成したのは、二分探索アルゴリズム、またはそれに近いものです。このアルゴリズムは O(log n) です。