Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Anonymous asked in 電腦與網際網路程式設計 · 1 decade 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++)






2 Answers

  • Leslie
    Lv 7
    1 decade 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 補充:









    其中, 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)

  • 1 decade ago


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


    你真的好厲害> <


Still have questions? Get your answers by asking now.