bob*_*bob 7 sorting algorithm time-complexity
经典的计数排序示例要求您构建一个大小等于输入数组的最大整数的数组.
例如,如果您的数组是[1,6,3,30000,8],则需要一个10000长的数组用于计数排序.
这可能不是在整数上使用哈希表在相同的线性时间内完成的吗？只是一张简单的地图？
在python中,它是这样的:
counting_map = {n: 0 for n in input_array} # start by mapping all to 0
for num in input_array:
counting_map[n] += 1
我知道这对整数来说真的很有效,但在这种情况下,映射解决方案并不优越吗？
时间复杂度方面,您在O(n)时间初始化映射,然后在O(n)时间内遍历数组,然后在O(1)时间内对输入执行散列函数.(显然,大O符号不是算法是否良好的最终决定因素,我只是想确保我的理论在这里是正确的).
这是一个很好的解决方案,还是"原始"计数排序还能做出一些我看不到的优势？我也很好奇为什么"基于散列图的计数排序"几乎不会返回任何谷歌搜索结果,使它看起来几乎没有使用过.散列的开销是否足以超过其较小的内存占用量？