Ordinary programmer
2019-09-02 18:37
采纳率: 42.9%
浏览 1.6k

基数排序的空间复杂度求助!

时间复杂度(维基百科)

维基百科

对{123,423,412,023}进行基数排序,B是10,蓝色部分N是10^3
对{as,qe,sd,fa,as,ws}进行基数排序,B是26,蓝色部分N是26^2

k就是:位数(也可以理解为需要排序得趟数)

空间复杂度?

维基百科说是
图片说明

王道和天勤考研书都是O(r),r是队列数(桶子数)

假设用r个队列模拟r个桶子,需要头尾指针,2r

可是你存放队列之后,那n个数据再存放进队列中,不是n??

我觉得空间复杂度是O(n+r)

2条回答 默认 最新

相关推荐 更多相似问题