为什么bucket sort的space complexity是O(kn)

问题不是很复杂，就是bucket sort的time complexity是O(n+k)这个可以理解。但是关于空间的话，为何是O(kn)。比如有1~100的N个整数，如果放到k个Bucket里面，每个bucket如果是一个range的话，N个数是分配到k个bucket里面，如果每个bucket的大小不固定，比如用arraylist，不应该是(n/k)*k=O(n)么，表示不理解。希望大家指点下。

弱弱能问一下Bucket Sort的中文名是啥？。。。。

刚看下wiki.....我觉得最后的concatenation of buckets[0], ..., buckets[n-1]　导致的吧

readman 发表于 2014-1-16 23:50
刚看下wiki.....我觉得最后的concatenation of buckets[0], ..., buckets[n-1]　导致的吧

还是不太懂

arraylist插入一个新的元素不一定是常数时间

而如果不用这种“自增长”的数据结果，那么每个bucket都得是长度n的array

bb4ever 发表于 2014-1-19 04:33
arraylist插入一个新的元素不一定是常数时间

而如果不用这种“自增长”的数据结果，那么每个bucket都得是 ...

arrayList 每次double它自身的长度

readman 发表于 2014-1-20 07:54
arrayList 每次double它自身的长度

再解释一下
插入新的元素如果超过capacity自然要double长度
double完了还要把原array的元素复制到新array当中，这不是常数时间

bb4ever 发表于 2014-1-19 04:33
arraylist插入一个新的元素不一定是常数时间

而如果不用这种“自增长”的数据结果，那么每个bucket都得是 ...

可以理解为worst case每个bucket都要开一个length=n的array，所以是O(nk)。那如果每个Bucket用linkedlist就不需要，在很多情况下可以减少至O(n)么

nkbuaayl 发表于 2014-1-21 05:55
可以理解为worst case每个bucket都要开一个length=n的array，所以是O(nk)。那如果每个Bucket用linkedlist ...

虽然用linked list可以把空间代价减少到O(n)。
但是分完bucket之后，每个bucket之中都会有多个元素，你要继续在每个bucket里面进行排序。
就是在linked list上进行排序，时间代价就不像你写的那么美好了。

看问题要有个big picture
时间和空间都是相互关联的，而很多时候大家的目标都是在保持相同的时间代价下提升空间或反过来。