-1

私はこのトピックについて少し混乱しています。

リストがすでにソートされている場合、最高のパフォーマンスは n であると言います。

また、バブル ソートなどの一部のアルゴリズムでは、最悪のケースは n^2 であると言います。

私の混乱は、なぜ n^2 と言うのですか?? その四角はどうやってできたのですか？正方形を維持するために私たちが行っている仮定は何ですか? O(1)、O(log n)、O(n)、O(2^n) のように与えないのはなぜですか?? これらの用語を理解するのを手伝ってください...記事、ブログ、講義ノート..何でも役に立ちます。

私は初心者です。

4

5 に答える 5

0

バブル ソート (または実際には任意のソート) を理解するには、それが使用するプロセスを熟考する必要があります。たとえば、バブル ソートは、リスト全体をスキャンし、場違いなペアを交換することによって機能します。最悪の場合、最初のパスで n - 1 回のスワップを行い、n 個の要素すべてを調べます。2 番目のパスでは、最後の要素が最後まで「バブリング」されるため、順序どおりであることが保証されます。したがって、並べ替えでは、n - 1 個の要素を調べて、最大で n - 2 個のスワップを行う必要があります。したがって、O(n^2) の最悪のシナリオです。

並べ替えの仕組みを理解できれば、最良のシナリオと最悪のシナリオを計算できます。ウィキペディアで始めることができます：

http://en.wikipedia.org/wiki/Sorting_algorithm

PS -- バブル ソートは、これまでで最悪のソートです。ただし、並べ替えられたデータを並べ替える場合は、他の方法よりも優れたパフォーマンスを発揮します。

于 2013-04-30T01:13:19.830 に答える
0

これがあなたが探しているものだと思います。

http://en.wikipedia.org/wiki/Best,_wost_and_average_case

于 2013-04-30T05:47:40.887 に答える
0

以下の単純なプログラムがあり、その時間計算量を求めたいとします。

return_sum(n)
{
y=4

while(n>0)
{
y=y+y
n=n-1
}
return y
}

コンピュータプログラムは一連のステップで構成されています。プログラムの時間の複雑さは、プログラムが特定の問題を解決するために必要なステップの数と考えることができます。

return_sum() プログラムに必要なステップ数:

return_sum(n)
{
y=4      // this step will take constant time say, c1, and will run only once

while(n>0)  //this step run n time , if step takes c2 time , total time is n * c2
{
y=y+y     // this step will run n-1 time , total time (n-1) * c3
n=n-1    // this step will run n-1 time , total time (n-1) * c4
}return y    // takes constant time c5, run once.
}

このプログラムを実行するすべてのステップにかかる時間を追加しましょう

    = c1 + n * c2 + (n-1) * c3 +  (n-1) * c4 +c5 
    =  n(c2 + c3 + c4 ) + (c1+ c5 - c2 - c3)

(c2 + c3 + c4 ) と (c1+ c5 - c2 - c3) が定数である場合、それらを a および b として表すことができます。

   =an + b

これは n の関数です。

f(n) = an+b

そして、この関数は O(n) です。したがって、このプログラムの時間計算量は O(n) です。

証拠：

f(n)  = an+b

Lets give a and b any constant values , suppose a = 100 and b = 200

Now for all sufficient large value of n >=1.
                                         100n  < 200n
 and                                    
                                         200    <  200n

                  f(n)=100n+200   < 200n + 200n
                                  < 400n                   
                                  < 400 * n             where c = 400 and n0 = 1
                              f(n)= O(n)

ここに画像の説明を入力

同様に、挿入ソートですべてのステップを追加すると、f'(n) が得られます。

                     f'(n) = an^2+bn+c

上記の証明により、f'(n) = O(n^2) が簡単にわかります。

于 2013-04-30T12:49:01.437 に答える
0

たくさんの答えがたくさんありますが（いくつかは素晴らしいものです）
、愚かな人にとっては十分に単純なものではない
ので、試してみます：

in: 0,3,7,8 ... n=4 最良のシナリオ
1. 0,3 ,7,8
2. 0, 3,7 ,8
3. 0,3, 7,8
- 変更は発生しないので、そのソート... O(n-1) -> ~O(n)

in: 8,7,3,0 ... n=4 最悪のシナリオ
1. 7,8 ,3,0
2. 7, 3,8 ,0
3. 7,3, 0,8
- 変化が起こったまだ止まらない
4. 3,7 ,0,8
5. 3, 0,7 ,8
6. 3,0, 7,8
- 変化があったのでまだ止まらない
7. 0,3 ,7,8
8. 0 , 3,7 ,8
9. 0,3, 7,8
- 変更がないため、ソートされます ... O((n-1)^2) -> ~O(n^2)

私がどこかでばかげた間違いをしなかったことを願っています...そしてそれはもちろん誰かを助けます.

于 2013-10-29T11:58:04.920 に答える