忍者ブログ

ま、お硬く言うと「ソートアルゴリズムの複雑性」ですね。

つわけで、「GREサブジェクトテストCS分野の問題(PDF)を解こう!」の続き。



ほいで第三問は、「バブルソート、マージソート、ヒープソート、クイックソート、トーナメントソートのうち、実行時間が最悪の場合Θ(n ²)かかるけど、平均ではΘ(n logn )のものは、どれ?」というもの。

これは、まあ、「暗記物」ですね。代表的なソートに関しては、ベストとアベレージとワーストの実行時間を覚えておけ、と。

つわけで、以下に、問題文に挙がっているソートについて、ワーストとアベレージの実行時間を列挙しときます。

ソート名 ワースト アベレージ
バブル Θ(n ²) Θ(n ²)
マージ Θ(n logn ) Θ(n logn )
ヒープ Θ(n logn ) Θ(n logn )
クイック Θ(n ²) Θ(n logn )

(「トーナメントソート」って聞いたことないんですけど……)



で、これらソートアルゴリズムはけっこう重要だし、それに、アルゴリズムの複雑さがらみの問題も頻出なんで、別項を設けて、それらのことについてあとで書きたいなあ、と思っとります……が、腹減ったんで今はとりあえず飯食います。

では。

PR
この記事にコメントする
お名前
メールアドレス
URL
コメント
それって、N-P完全問題なんかとも関係あるんですか?
宮本浩樹 2005/09/25(Sun)23:17:00 編集
NP完全問題って、要はアルゴリズムの複雑さの話だから、関係ありあり。

で、あるアルゴリズムがクラスNPに属するか否かを問う問題ってのは、この問題集だとけっこう後のほうでの登場になるんだけど、次にアップするアルゴリズムがらみのエントリで、ちょっと先回りしてNPの話もしますかね。

ま、予定は未定、だけど。
はやし 2005/09/25(Sun)23:43:00 編集
この記事へのトラックバック
この記事にトラックバックする:
カレンダー
05 2017/06 07
S M T W T F S
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30
最新コメント
[06/28 FerminBycle]
[06/27 カルティエ 指輪 クリーニング]
[06/27 ブランド激安 時計 0752]
[06/27 ブランド激安通販]
[06/26 バッグ ブランド激安]
[06/26 s品 n品]
[06/26 ルイビトン激安本物]
[06/26 グッチ 長財布 メンズ]
[06/26 ブルガリ カフェ 銀座]
[06/26 レディース財布 ブランド激安]
最新トラックバック
メール
ブログ作成者(はやし)に直接訴えたいことがある、という場合は、下のアドレスにメールをどうぞ。

thayashi#ucalgary.ca
(#を@に置換してください)

ブログ内検索
Google
WWW を検索 このブログ内を検索

はやしのブログ内で紹介された
 書籍の検索はこちら
 音盤の検索はこちら
ランダムおすすめ
(忍者ブログに引越してから、うまくうごかなくなってしまいました。いつか、直します)
Randombook
このブログで紹介したことのある本をランダム表示。
Randomusic
このブログで紹介したことのある音をランダム表示。
自分がらみのリンク
はやしのブログ書籍一覧
このブログで言及された書籍の一覧。
はやしのブログ音盤一覧
このブログで言及された音盤の一覧。
最近のおすすめ本
最近のおすすめ音

Copyright © [ はやしのブログ ]
No right reserved except those which belong to someone else.
Special Template : 忍者ブログ de テンプレート and ブログアクセスアップ
Special Thanks : 忍者ブログ
Commercial message : [PR]