Ordinary programmer 2019-09-02 18:37 采纳率: 33.3%
浏览 1872
已采纳

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

时间复杂度（维基百科）

维基百科

对{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）

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题？

悬赏问题

  • ¥15 FLUENT如何实现在堆积颗粒的上表面加载高斯热源
  • ¥30 截图中的mathematics程序转换成matlab
  • ¥15 动力学代码报错，维度不匹配
  • ¥15 Power query添加列问题
  • ¥50 Kubernetes&Fission&Eleasticsearch
  • ¥15 報錯：Person is not mapped，如何解決？
  • ¥15 c++头文件不能识别CDialog
  • ¥15 Excel发现不可读取的内容
  • ¥15 关于#stm32#的问题：CANOpen的PDO同步传输问题
  • ¥20 yolov5自定义Prune报错，如何解决？