ノート:ソート

バケットソートの最悪計算時間

英語版のノートでも話題に挙がっていますが、バケットソートの最悪計算時間が 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)