sorting - カウントと基数ソートの実行時間

Question

カウントと基数の並べ替えは、一般に O(n) 時間で実行されると考えられていることを知っており、その理由も理解していると思います。ただし、割り当てで、これらの並べ替えが O(n) 時間で異なる正の整数のリストを必ずしも並べ替えるとは限らない理由を説明するように求められています。理由が思いつきません。

どんな助けでも大歓迎です！

Answer 1

カウントまたは基数ソートが O(n) であると言うのは、実際には正しくありません。

ソートのカウントは O(n+k) です。ここで、k は配列内の任意の要素の最大値です。

その理由は、リスト全体をステップ実行してカウント (O(n)) を入力してから、カウント (O(k)) をステップ実行する必要があるためです。

基数ソートは O(mn) で、m は数値の最大桁数です。

その理由は、配列を 1 桁ごとに 1 回 (O(n) m 回) 実行する必要があるためです。