假设我们有 m 个集合 S1,S2,...,Sm来自 {1...n} 的元素
鉴于 m=O(n) ，|S1|+|S2|+...+|Sm|=O(n)
在 O(n) 时间和 O(n) 中对所有集合进行排序空间。
我想在每个集合上使用计数排序算法。
每组的计数排序将为 O(S1)+O(S2)+...+O(Sm) < O(n)
因为在最坏的情况下，如果一个集合由 n 个元素组成，它仍然需要 O(n)。
但是它会解决问题并仍然认为它仅使用 O(n) 空间吗？
最佳答案
您的方法不一定能在 O(n) 时间内奏效。假设您有 n 组，每组一个元素，其中每组仅包含 n 个。那么计数排序的每次迭代都将花费 Θ(n) 的时间来完成，因此总运行时间将为 Θ(n2)。
但是，您可以使用修改后的计数排序来解决此问题，方法是同时对所有集合进行有效的计数排序。创建一个长度为 n 的数组，用于存储数字列表。然后，遍历所有集合，对于每个元素，如果值为 k 且集合编号为 r，则将编号 r 附加到数组 k。这个过程实质上是建立了集合中元素分布的直方图，其中每个元素都用它来自的集合进行了注释。然后，迭代数组并使用类似于计数排序的逻辑按排序顺序重建集合。
总的来说，该算法需要时间 Θ(n)，因为初始化数组需要时间 Θ(n)，分配元素的总时间为 O(n)，写回元素的时间为 O(n)。它也仅使用 Θ(n) 空间，因为总共有 n 个数组，并且在所有数组中总共分布有 n 个元素。
希望这对您有所帮助!
关于algorithm - 对 O(n) 中的 m 组总 O(n) 元素进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19960467/