给定具有 n 个元素 [1,...,n] 的数组的最大元素 M，每个基于比较的排序算法的时间复杂度下限 Ω(nlogn) 如何受到影响？我必须强调给出了数组的最大元素 M。
问问题
551 次
2 回答
3
它不受影响。
请注意，存在n!可能的排列，并且每个比较 OP 都有 2 个可能的结果——“左更高”或“右更高”。
对于任何基于比较的算法，每个“决定”都是根据一次比较的结果做出的。
因此，为了成功确定任何排列的正确顺序，您将需要（在最坏的情况下）log 2 (n!) 比较。
但是，众所周知，log 2 (n!) 在 Theta(nlogn) 中 - 无论手头的范围如何，您都会回到 Omega(nlogn) 的下限。
请注意，存在其他不使用（仅）比较的方法来更有效地对整数进行排序。
于 2013-12-24T17:01:29.250 回答
1
如果M确实是数组元素的绝对值的界限，并且元素是整数，则可以及时对数组进行排序O(n + M)，方法是将单独的数组int occurrences[2M + 1];初始化为0，扫描原始数组并计算每个数组的出现次数元素，并使用 . 写入输出数组occurrences。
如果元素是浮点数（正式地，实数），则对它们的大小进行限制没有效果。
如果元素是整数并且可以是负数（正式地，任意大大小的整数），那么对大小设置上限没有影响。
编辑：在O(n)第一段中，应该是O(n + M).
于 2013-12-24T17:02:59.403 回答