Hab*_*bit 2 sorting algorithm big-o
我正在努力弄清楚哪些算法最适合某些规格使用.
这是提示:
写一个算法来排序n个整数,每个整数在O(n)时间范围内[0 ..((n ^ 4)-1)].
我更像是一个视觉学习者,并通过实例最好地理解.我为此设计了值以使其可视化,但我不知道使用什么排序方法或如何确定使用哪种方法.任何提示或建议都非常感谢.谢谢!
就像我在评论中所说的那样,据我所知,唯一的方法就是基数排序.您基本上通过分别比较每个数字对数字进行排序.
该算法的完整复杂性为O(d(n + b)),其中b是所选择的基础,d是该基础中的位数.您可以选择任何基础,并在此基础上使用数字.
这里的诀窍是选择正确的基础.有一个基础可以使算法O(n),但如果你只使用基数2,每个数字将有最多O(4 logn)数字,因此总复杂度将是O(n logn).
作为提示,存在这样的基础,其中该范围中的每个数字将具有恒定的数字位数.