Anonymous
Anonymous asked in 電腦與網際網路程式設計 · 9 years ago

關於"資料結構"--Complexity的題目 >

Determine the frequency counts for all statements and

analysis the complexity for the program segment

for(int i=0;i<n;i++)

{ // n is number of elements stored in array

for (int j=0;j<n-i;j++)

{

if(array[j]>array[j+1])

Swap(array[j],array[j+1]);

}

}

2 Answers

Rating
  • Leslie
    Lv 7
    9 years ago
    Favorite Answer

    This program sorts the n numbers in non-decreasing order and

    the algorithm used is called "bubble sort".

    (這程式會把 n 個數從小排到大, 其使用的演算法稱為 "氣泡式排序法")

    n 個資料在 A[0], A[1], ..., A[n-1].您的程式有錯:

    其中的兩個 for 當中的結束條件應該是 i<n-1 及 j <n-i-1

    否則, array A 會使用到 A[n], 這是超出 array 的標註.(1) 考慮 array[j]>array[j+1] 的 frequency count由於 i=0, 1, 2, ...,n-2, 而且, 對於每個 i 時,

    j 會從 j=0, 1, 2, ..., n-i-2.

    因此 i=0 時, 迴圈中的 array[j]>array[j+1] 會做 n-1 次,

    i=1 時, 迴圈中的 array[j]>array[j+1] 會做 n-2 次,

    i=2 時, 迴圈中的 array[j]>array[j+1] 會做 n-3 次,

    ... ... ...

    i=n-2, 迴圈中的 array[j]>array[j+1] 會做 1 次.

    所以 array[j]>array[j+1] 會總共做

    (n-1)+(n-2)+...+1 次 = n(n-1)/2 次(2) 考慮 Swap 的 frequency count

    當 array[j]>array[j+1] 執行一次時,

    Swap 可能做一次, 或不做.

    因此 Swap 最多做 n(n-1)/2 次 (worst case), 最少做 0 次

    (前者發生在 n 個數原來是從大排到小,

    後者發生在原來 n 個數已經從小排到大了).

    每個 Swap 會使用 3 個基本運算 (即,

    t=array[j]; array[j]=array[j+1]; array[i+1]=t;) -- 不會影響整個的

    complexity.(3) 為了控制迴圈, i 及 j 須要每次增加 1, 並且要檢查結束條件,

    這些總共的運算次數是和 (1) 同樣的 complexity.由 (1)+(2)+(3), 知道,

    total frequency counts 是一個 n 的二次函數,

    因此 complexity 為 O(n^2).

    2010-10-04 20:58:46 補充:

    用 tabular method (我不認為這是好方式), 即, 考慮每個 statement 的

    s/e; frequency; total steps, 如下:

    2010-10-04 21:06:24 補充:

    1.__1__n+1__n+1

    2.__0___0___0

    3.__1___X___X

    4.__0___0___0

    5.__1___Y___Y

    6.__1___Z___Z

    7.__0___0___0

    8.__0___0___0

    其中, X 是 n+(n-1)+(n-2)+...+1=n(n+1)/2

    Y 是 (n-1)+(n-2)+(n-3)+...+1=n(n-1)/2

    Z 是 0~n(n-1)/2 (即 0 到 n(n-1)/2)

    • Login to reply the answers
  • 9 years ago

    如下...不見了>

    2010-10-04 21:09:23 補充:

    謝謝你....

    你真的好厲害> <

    下次有機會希望您還能幫我解答^^

    • Login to reply the answers
Still have questions? Get your answers by asking now.