排序大小为k的problem- N/K的间隔的每个

鉴于是大小Ñ的阵列，其被划分到N/K大小ķ每个间隔。每个区间中的值大于其左侧区间中的值，并小于右侧区间中的值。我想在尽可能短的时间内对这些值进行排序。排序大小为k的problem- N/K的间隔的每个

，我认为的幼稚溶液仅仅是在每个间隔中的所有值进行排序，其将“成本” O（ķ日志k）的，对于所有的N/K的间隔总成本O（n log k）。我想知道是否有更有效的东西。

现在我知道在每个区间我不会有超过的日志日志k不同的值，我需要想出一个更快的算法。我很乐意为你提供帮助。

谢谢！

2011-07-09 Numerator

如果你使用平衡二叉树，你现在的方法是用O（n logloglog（k）），因为对于排序的二叉搜索树深度最多为O（log（log log k）），所以对于其中一个间隔O （k日志日志日志k），我认为这种方法是足够快，也没有任何特定的关系在你的区间，以提高n * X g（n）* X，所以我认为你不能减少' N'。 –

对于'n \ k'，你的意思是'n/k'，即“n除以k”？ – Svante

@Svante：是的，这就是我的意思 – Numerator

下面是一个极其丑陋的答案：

1. Take the first interval; 
2. Since logK should be small, we allocate logK binary tree nodes, and we place the first element in the middle; 
3. For the rest of the elements, we use method similar to binary search to search if it is already included, or we add this element; 
4. Produce a sorted list with all the values in the interval; 
5. Use Counting Sort with this list on the interval; 
6. Do this for all the intervals.

用于2,3的时间是O（K * logloglogK），因为搜索需要最多logloglogK（登录的loglogK元素），并重复K次。 4最多使用O（loglogK）时间遍历所有具有值的节点。 5需要O（K）时间，与Counting Sort相似。所以总时间应该是O（nlogloglogK）。

任何问题都很受欢迎，因为我很困，并不能保证我在思考。

来源

2011-07-09 07:40:15

你可以在每个间隔为每一个成本O(k) 使用counting sort或bucket sort，为O(n/k * k) = O(n)

总成本然后合并每个间隔一起花费在总O(n)。你的算法将是一个O(n) + O(n) = O(n)算法。

注意：如果您可以利用并行性，则可以并行排序所有间隔，总成本为O(k)。虽然你的算法仍然是O(n)（由于合并），它将有较小的常数因子。

来源

2011-07-09 12:18:58 Aly

排序大小为k的problem- N/K的间隔的每个

回答

相关问题