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

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

时间复杂度(维基百科)

维基百科

对{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条回答 默认 最新

  • Ordinary programmer 2019-09-07 01:00
    已采纳

    实际空间复杂度是:O(n+r)
    但是在考虑额外空间复杂度,由于本身基数排序是内部排序(数据存放在内存),会占用O(n)
    这里就将它认为:O(r)

    就像认为冒泡排序,直接选择排序,空间复杂度是:O(1),但是实际应该是O(n)

    点赞 打赏 评论
  • dabocaiqq 2019-09-06 08:36
    点赞 打赏 评论

相关推荐 更多相似问题