0

バブルソートが200の名前をソートするのに200秒かかる場合、800秒で何個のアイテムをソートできますか？

比較の数を計算すると、解決策が得られます。200個の名前を並べ替えるのに必要な比較の数をどのように計算できますか？最良のケースを検討する必要がありますか？

4

2 に答える 2

1

800 は 4 x 200 です。バブル ソートは O(n*n) であるため、平均して 4 倍の時間で 2 倍のアイテムをソートできるため、200 が平均的なケースである場合、平均で 400 の名前が期待されます。

于 2012-10-08T11:23:19.273 に答える
1
  1. バブルソートはO(n 2 )です。あなたの計算を行います。Big O は相対的な時間のアイデアを提供するだけで、時間の大まかな見積もりを推測できます。正確ではありません。
  2. BubbleSort は、最初は n-1 回、2 回目は n-2 回というように比較を行います。したがって、合計があり(n-1) + (n-2) + .. +1ます。もう一度数学をしますか？
  3. バブルソートが可哀想すぎてベストケースがない！[1]

(明らかに、既にソートされた配列をソートしないスマートバブルソートを書くことができます)

BUBBLESORT A
 for i = 1 to A.length 1
  for j = A.length downto i+1
    if A[j]  < A[j - 1]
     exchange A[j] with A[j-1]

アルゴリズムの紹介から - CLRS

[1] #3について。http://en.wikipedia.org/wiki/Bubble_sortを参照してください。ソートされた残りの配列を識別し、最良のケース O(n) を作成する最適化された内部ループについて言及しています。それについては申し訳ありません。

于 2012-10-08T09:38:24.847 に答える