假设我们有 m 组S1,S2,...,Sm元素来自{1...n}
Given that m=O(n) ，在 O(n) 时间和空间|S1|+|S2|+...+|Sm|=O(n)
内对所有集合进行排序。O(n)
我正在考虑在每组上使用计数排序算法。对每个集合进行计数排序O(S1)+O(S2)+...+O(Sm) < O(n)
，因为在最坏的情况下，如果一个集合由 n 个元素组成，它仍然需要 O(n)。
但它会解决问题并仍然坚持它只使用 O(n) 空间吗？
问问题
139 次
1 回答
2
您的方法不一定会在 O(n) 时间内起作用。想象一下，你有 n 个集合，每个集合一个元素，每个集合只包含 n 个元素。然后计数排序的每次迭代将花费时间 Θ(n) 来完成，因此总运行时间将为 Θ(n 2 )。
但是，您可以通过同时对所有集合有效地进行计数排序来使用修改后的计数排序来解决此问题。创建一个长度为 n 的数组，用于存储数字列表。然后，遍历所有集合，对于每个元素，如果值为 k 且集合编号为 r，则将数字 r 附加到数组 k。这个过程基本上建立了集合中元素分布的直方图，其中每个元素都用它来自的集合进行注释。然后，迭代数组并使用类似于计数排序的逻辑按排序顺序重建集合。
总的来说，这个算法需要时间 Θ(n)，因为初始化数组需要时间 Θ(n)，分配元素的总时间是 O(n)，写回它们需要 O(n) 时间。它也只使用 Θ(n) 空间，因为总共有 n 个数组，并且在所有数组中总共分布有 n 个元素。
希望这可以帮助！
于 2013-11-13T17:48:42.233 回答