a1023182899
Ordinary programmer
采纳率50%
2019-09-02 18:37

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

时间复杂度(维基百科)

维基百科

对{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条回答

  • a1023182899 Ordinary programmer 2年前

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

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

    点赞 评论 复制链接分享
  • dabocaiqq dabocaiqq 2年前