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

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),要怎麼分析呢

感謝

1 個解答

評分
  • sponge
    Lv 6
    7 年前
    最佳解答

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

    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) 不受影響,這邊複雜度只跟迴圈寫法有關

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

還有問題?馬上發問,尋求解答。