关于基数排序最坏空间复杂度
http://en.wikipedia.org/wiki/Radix_sort

根据维基记载，基数排序时间和空间复杂度均是：O(kn)



时间复杂度还好理解，但最坏空间复杂度我不知道为什么是O(kn)

以其中的Iterative version using queues的实现为例，
n=10
k=3
用到了大小为10的array和大小同样为10的queue，这样的话空间复杂度照理只有O(2n)，不知道什么情况下会是O(2n)，也即O(kn)



[解决办法]
取决于数组的数结构。
例如，如果数组元素正好是1~n，每个数出现一次，则显然k=1.

[解决办法]
因为你有n个数，每个数k位，所以存下所有n个数需要O(kn)空间。
计算机里有一个int能存一个数会让人误以为O(1)就能存下一个数。但是其实不是的。有k位就得用O(k)的空间才能存下一数。