ここから本文です

平均計算量のオーダーが最も小さいソートアルゴリズム(外部記憶領域を用いず、対...

yrt********さん

2016/8/3000:22:44

平均計算量のオーダーが最も小さいソートアルゴリズム(外部記憶領域を用いず、対象データに何らかの制約を課さないという条件の下で)は何でしょうか?
例えば、O(nlogn)より速いものは存在しますか?

よろしくお願いいたします。

この質問は、活躍中のチエリアン・専門家に回答をリクエストしました。

閲覧数:
46
回答数:
2

違反報告

ベストアンサーに選ばれた回答

プロフィール画像

カテゴリマスター

nor********さん

2016/8/3002:02:09

平均計算量のオーダーとしては外部領域を使わないという条件では
・クィックソート
・マージソート
。ヒープソート
などががO(n Log n)だと思います。
基数ソートのオーダーはこれらよりも小さいが外部領域が必要のはずです。

・クィックソートは平均的には最速だが最悪の場合はO(n**2)
・マージソートは基本的にマージするためのメモリが必要
・ヒープソートも最悪でもO(n Log n)だが、実際の平均処理時間はクィックソートより劣る

だったと思います。

質問した人からのコメント

2016/8/30 08:06:16

ありがとうございます!

ベストアンサー以外の回答

1〜1件/1件中

ksk********さん

2016/8/3000:54:07

ソートしたいデータの条件によるとしか言えないけど
安定して早いのは
クイックソートとかマージソートとか

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる