我正在尝试创建一种算法，可以在 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)
我不确定如何进行归纳步骤(如果需要的话)。
最佳答案
以下屏幕截图对此进行了解释:
关于algorithm - 在 O(n) 时间内对 0...n 之间的 n 个数字的整数数组进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9082868/