基数ソートの時間計算量はO（kn）です。ここで、nはソートされるキーの数、kはキーの長さです。同様に、トライでの挿入、削除、およびルックアップ操作の時間計算量はO（k）です。ただし、すべての要素が異なると仮定すると、k> = log（n）ではありませんか？もしそうなら、それは基数ソートの漸近的な時間計算量がクイックソートのそれと等しいO（nlogn）であり、トライ操作が平衡二分探索木のそれと等しいO（logn）の時間計算量を持っていることを意味します。もちろん、定数係数は大幅に異なる場合がありますが、漸近的な時間計算量は異なりません。これは本当ですか？もしそうなら、基数ソートと試行には他のアルゴリズムやデータ構造に勝る他の利点がありますか？
編集：
クイックソートとその競合他社はO（nlogn）比較を実行します; 最悪の場合、各比較にはO（k）時間がかかります（キーは最後の桁がチェックされたときにのみ異なります）。したがって、これらのアルゴリズムにはO（knlogn）時間がかかります。同じ論理で、平衡二分探索木操作にはO（klogn）時間がかかります。
Big O 表記はそのようには使用されません。基数ソートで k>=log n であっても、O(kn) は n が 2 倍になると処理時間が 2 倍になることを意味します。これが big-o 表記の使用方法です。
基数ソートの利点の 1 つは、最悪の場合が O(kn) (クイックソートの O(n^2)) であるため、基数ソートはクイックソートよりも悪意のある入力に対して何らかの形で耐性があることです。また、ビット単位の演算、ベースとして 2 の累乗、および小さい配列の挿入ソートを使用したインプレース msd-radix ソートを使用すると、実際のパフォーマンスの点で非常に高速になる可能性があります。
同じ議論が試行にも当てはまります。最悪の場合、挿入/検索が O(k) であるという意味で、悪意のある入力に対して耐性があります。ハッシュテーブルは O(1) で挿入/検索を実行しますが、O(k) ハッシュを使用し、最悪の場合は O(N) 挿入/検索を実行します。また、try は文字列をより効率的に格納できます。
アルゴリズムの複雑さの攻撃を確認する
基数ソートの漸近的な時間計算量はO（NlogN）であり、これはQucikソートの時間計算量でもあります。基数ソートの利点は、クイックソートの最悪の場合のパフォーマンスがO（N ^ 2）であるのに対し、最良、平均、および最悪の場合のパフォーマンスが同じであるということです。ただし、クイックソートで必要な2倍のスペースが必要です。したがって、スペースの複雑さが問題にならない場合は、基数ソートの方が適しています。