mar*_*gor 4 sorting algorithm asymptotic-complexity radix
基于这个基数排序文章http://www.geeksforgeeks.org/radix-sort/我正在努力理解在排序中某些方法的时间复杂性方面正在解释什么.
从链接:
让输入整数有d位数.基数排序采用O(d*(n + b))时间,其中b是表示数字的基数,例如,对于十进制系统,b为10. d的值是多少？如果k是最大可能值,则d将是O(log_b(k)).因此总体时间复杂度为O((n + b)*logb(k)).对于大k来说,这看起来不仅仅是基于比较的排序算法的时间复杂度.让我们先来限制k.设k≤nc,其中c是常数.在这种情况下,复杂性变为O(nlogb(n)).
所以我确实理解排序需要O(d*n),因为有d个数字因此d遍,你必须处理所有n个元素,但我从那里丢失了它.一个简单的解释将非常有用.
小智 6
假设我们使用桶排序对每个数字进行排序:对于每个数字(d),我们处理所有数字(n),将它们放入桶中以获取数字可能具有的所有可能值(b).
然后,我们需要处理所有桶,重新创建原始列表.将所有项放在存储桶中需要花费O(n)时间,从所有存储桶重新创建列表需要花费O(n + b)时间(我们必须迭代所有存储桶及其中的所有元素),并且我们对所有数字执行此操作,给出运行时间O(d * (n + b)).
这只是线性的,如果d是常数并且b不是渐近地大于n.事实上,如果你有多少log n比特,那就需要O(n log n)时间.