algorithm - 在 O(n) 时间内对从 0...n 到 n 位的整数数组进行排序

Question

我正在尝试创建一种可以在 O(N) 时间内对整数数组进行排序的算法。

• 所有整数的位数是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

我提出的解决方案是 ∑k*∑n 将始终等于 N。

尝试证明

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

我不确定如何进行归纳步骤(如果需要的话)。

Answer 1

下面的截图解释了它: