0

Big Ohは、ソートアルゴリズムに対してどのように計算されますか？選択ソート、マージソート、挿入ソートを使用して、カードのデッキ（n = 52）をソートするプログラムを作成しました。ソートアルゴリズムごとに、計算コストを計算する必要があります。どうすればいいのですか？

今、私はそれが私の宿題の一部であることを認めるのに十分正直ですが、私はただ助けを求めています。私はBigOh表記法に不慣れで、いくつかのWebサイトを調べましたが、並べ替えアルゴリズムの観点からそれを理解できませんでした。

少なくとも誰かが私にヒントを与えることができますか？

選択ソート、挿入ソート、マージソートについてウィキペディアを参照しました。

挿入ソート：ベストケース：O（n）、ワーストケースおよびアベレージケース：O（n ^ 2）

選択ソート：3つのケースすべてでO（n ^ 2）

マージソート：3つのケースすべてでO（nlog n）

本当？

4

1 に答える 1

2

あなたが探しているのは複雑さと呼ばれ、あなたの場合はおそらく実行時間の観点からです。「BigO」は単に上限を表しますが、「small o」は下限を表し、平均は「Theta」です。これらは、スケーリングや加算とは関係なく、プログラムの実行に使用されるタイムステップの関数を表します。

例：並べ替えアルゴリズムがすべてのリスト（サイズn）の項目を1回（たとえばforループで）繰り返し、すべてのステップでもう一度ループする（そこでlステップを実行する）場合、約l * n*nステップが必要になりますさらに、準備などのためにいくつかのkステップが実行されます。これにより、lとkが一定であるため、の複雑さがになります。これはO(l*n*n + k)、に等しくなります。O(n*n) = O(n^2)

より多くのより深い情報： http： //en.wikipedia.org/wiki/Time_complexity

于 2013-02-12T22:39:19.913 に答える