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

报告相同问题？

提交

相关推荐 更多相似问题

  • 基数排序的空间复杂度求助！ c++c语言开发语言
    2019-09-02 18:37
    回答 2 已采纳 实际空间复杂度是：O（n+r） 但是在考虑额外空间复杂度，由于本身基数排序是内部排序（数据存放在内存），会占用O（n） 这里就将它认为：O（r） 就像认为冒泡排序，直接选择排序，空间复杂度是
  • 算法导论 基数排序 ，，
    2016-09-24 02:56
    回答 1 已采纳 基数排序有从高位开始排序的 最高位优先(Most Significant Digit first)法，简称MSD法 。最低位优先(Least Significant Digit first)法，简称
  • 对基数排序的原理不理解 c语言
    2021-06-25 10:18
    回答 2 已采纳 因为十位数天然大于个位数，百位数天然大于十位数，每一次排序都是对同一数量级的排序。
  • 该如何学习嵌入式？看大佬的职业规划！
    2021-10-23 17:18
    张巧龙的博客 如果要问，排序算法有几种，恐怕只知道冒泡和希尔，不知道堆排序，快速排序，基数链式排序这些算法，更不知道还有内部排序和外部排序之分。查找算法只知道个基本的2分查找。对于树的查找算法一无所知。 怎么说呢？ ...
  • 编程新手导论
    2012-06-07 20:00
    wangluozhangleilei的博客 第二部分 导论，这一部分主要是关于编程的导论， (要懂得一点思想具备一点常识)《设计，编码，，与软工》（编程与思想）这一章解释了三种思想，原语，抽象，组合，，和软件开发的二个重要过程，，软件工程的相关...
  • 没有解决我的问题, 去提问