ノート:ソート

ページのコンテンツが他言語でサポートされていません。

バケットソートの最悪計算時間[編集]

英語版のノートでも話題に挙がっていますが、バケットソートの最悪計算時間が O(n^2) となる理由がわかりません。入力に関わらず O(nk) だと思います。--Nagae 2008年5月29日 (木) 22:44 (UTC)[返信]

履歴をたどってみると2007年4月2日の編集のようです。全項目がひとつのバケツに入るケースということですが、確かに英語版のen:Bucket sortは一定範囲の値をひとつのバケツに対応づけているのですね。日本語版のバケットソートは、バケツの中には同じ値しか入れていないので、ひとつのバケツに集中しても O(n) になるはずです。私はバケットソートというと日本語版の定義の方がしっくりくるのですが、いくつか文献をあたってみようと思います。--Nagae 2008年5月30日 (金) 12:40 (UTC)[返信]
「https://ja.wikipedia.org/w/index.php?title=ノート:ソート&oldid=28054699」から取得