請教一題程式的時間複雜度

Question

int a[8,26,5,77,1,61,11,60,15,49,19];
int n = 11;

int ptt(int x)
{
  int k = -1;
  int i= 0;
  int j = n-1;

  do{
        k = (i+j) / 2;
        if(a[k] <= x)
            i = k+1;
        else
            j = k-1;
      }while(i<=j);
       return k;
}

想請教這題的時間複雜度為何?
好像是O(log n)，要怎麼分析呢

感謝

sponge · Accepted Answer

先直接從您程式碼的寫法來分析最差狀況

n=11 且 a 也含 11 個元素，故 n 就是資料的數量

i=0, j=n-1 正好讓兩者定位在 a 的第一與最後一個元素

k=-1, 這種設定通常表示 "unknown"

迴圈中 k = (i+j) / 2, 表示每回合分析 i~j 的中間

k 正好在一半位置，故 i=k+1 和 j=k-1, 都使下一回合 i~j 範圍減半

所以每回合範圍都是上次的一半，直到 i~j 不是一個範圍

要分析時間複雜度，將處理過程分為「第一回合」與「第二回合之後」

一開始資料有 n 筆，一回合後變成 n/2 筆

所以第二回合之後時間記為 T(n/2), 表示處理 n/2 資料的時間

第一回合中有些判斷、賦值等只在該回合做常數次的敘述

這些敘述分析時就記為 1

所以處理 n 筆資料費時 T(n) = T(n/2) + 1

將這關係式展開分析：

T(n) = T(n/2) + 1 = T(n/4) + 1 + 1 ...

展開了 log n 次後，結果變成 T(1) + log n

T(1) 是分析一筆資料的時間，是個與 n 無關的常數

所以 T(n) = T(1) + log n) = O(log n), 以 2 為底

這程式應該是從 binary search 改過來的

但因為資料為排序，所以沒有搜尋的效果

不過 O(log n) 不受影響，這邊複雜度只跟迴圈寫法有關

希望以上解釋對您有幫助！

請教一題程式的時間複雜度

1 個解答