0

(a) 最悪の場合、(b) 最良の場合、(c) バブルの並べ替えを行う次の関数の平均的な複雑さは何ですか?

for i=1 to n-1 do
    for j=i to n-1 do
        if x[j]>x[j+1] then
            temp=x[j]
            x[j]=x[j+1]
            x[j+1]=temp
        end {if}
    end {for}
end {for}

複雑さをどのように正当化しますか?

4

3 に答える 3

3

最悪のケースは O(n 2 ) です。

平均的なケースも O(n 2 ) です。

この場合、if ステートメント内のコードは実行されませんが、最悪のケースも O(n 2 ) です。二次的な複雑さは、リストの内容に関係なく、2 つの for ループが 3 つのケースすべてで完全に実行されるという事実によるものです。

于 2013-03-06T14:53:40.883 に答える
0

最高、最低、平均の場合の効率が劇的に変化するバブルソートアルゴリズムが必要な場合は、これを試してください。

int count = n - 1;    // The input size
bool sFlag = true;    // A flag variable allowing the inner outerloop to 
                         break early and fall through

while (sFlag ){

    sFlag = false;    // Set false so that the loop can break if no swaps occur
    for (int j = 0; j < count; j++){
        if (A[j+1] < A[j]){

            int temp;    // Swap the two elements
            temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;

            sFlag = true;    // A swap has occured, iterate again
        }
    }
    count--;    //Next time, don't bother looking at the last element, it is 
                  in order

}

これの最悪のケースは Cwost(n) = 1/2n(n+1) で、最良のケースは Cbest(n) = n-1 です。これは、カウント変数が、入力サイズに対して既に行われた反復の量に基づいて、内側のループの反復を少なくするためです。

これは、これまでに出会った中で最も効率的なバブル ソートです。

于 2016-04-21T06:59:50.157 に答える
0

while も O(n) であるため、以下の BubbleSort アルゴリズムにも当てはまります。

public static void BubbleSort( int [ ] num )
    {
        int j;
        boolean flag = true;  
        int temp;  

        while ( flag )
        {

            flag= false;   
            for( j=0;  j < num.length -1;  j++ )
            {
                if ( num[ j ] > num[j+1] )   
                {
                    temp = num[ j ];                //swap elements
                    num[ j ] = num[ j+1 ];
                    num[ j+1 ] = temp;
                    flag = true;              //shows a swap occurred
                }
            }

        }

    }
于 2013-10-16T20:28:54.190 に答える