基数を基数ソートで変更する

Question

基数ソートについて知りましたが、まだ何かを把握することはできません。

私の最大番号はn ^c（cは一定）としましょう。数値の基数を常にnに変更できるので、最悪の場合の複雑さはO（n）になりますか？

もしそうなら、配列をソートする最良の方法ではないのは、最大値O（n）を見つけて基数ソートを使うことでしょうか？

Answer 1

二つの独立した質問がここにあります

1. 配列の最大値が一定の定数cのためのn ^Cである場合には、必ず（n）の時間Oを取るベースで基数ソートのないn個？

2. 配列の中で最大の値を見つけて、基数nの基数ソートを使用するとどのくらいの複雑さがありますか？

質問（1）については、ランタイムがO（n）になることが間違いありません。基数ソートのコストはO（n log _b U）です。ここでbは基数ソートの基底であり、Uは配列の最大値です（これは数値がΘ（ログ _b U ）base-b digits）を入力します。この場合、ランタイムはcが固定定数であると仮定して、O（n log _n n ^c）= O（nc）= O（n）となります。

上記解析では、cが固定定数であることが事前にわかっていることに注意してください。。任意の整数値の配列を与え、基数nの基数ソートを使用すると、ランタイムはO（n log U/log n）になります。を事前に保証する場合はO（n）のみです。最大値が固定定数cに対して最大で^cであることを確認してください。これは一般的に真の文ではないので、基数ソートは常に時間O（n）で実行されるとは言えません。