O（n）時にn桁の0からnまでの整数の配列をソート

Question

O（N）の時間に整数の配列をソートできるアルゴリズムを作成しようとしています。

• intergersの全ての桁数がN
• ある各要素は数字
• の未知数を有するアルゴリズムに関係なく、数字が分散される方法のO（N）時間でアレイをソートする必要があり

私はこの問題の解決策を持っていますが、それはO（N）時間で実行されています。問題があることを証明しようとしています。

Create a set of N buckets and add items to their corresponding bucket based off how 
many digits are in the integer -O(N) 

Radix sort each bucket, and then concatenate the buckets back together. 
Sum k=0 to N of O(k*n) 
k = Number of digits 
n = number of items with k digits 

私が出ている解決策は、私は（誘導ステップを実行する方法がわからないんだ証明

Base case: Array has 1 item. 
T(N)= k*1. k=N = O(N) 

で∑k*∑nは常に等しいN.意志

試みということですそれが必要であれば）。

Answer 1

次のスクリーンショットは、それを説明する：