ソートproblem-サイズkのN/K間隔各

Question

はN/KサイズKそれぞれの間隔に分割されたサイズNのアレイです。各区間の値は、左の区間の値よりも大きく、右の区間の値よりも小さい。できるだけ早くそれらの値を並べ替える必要があります。

私は考えナイーブな溶液は、各区間のすべての値をソートするだけであるだろうの全てN/K間隔の総コストのために、「コスト」O（KログK）、 O（n log k）。もっと効率的なものがあるのだろうかと思います。

今私は、各時間間隔で、ログログkの値が異なることを知っています。より速いアルゴリズムを考え出す必要があります。私はこれであなたの助けが大好きです。

ありがとうございます！

Answer 1

ここで非常に醜いの答えだ：検索が最もlogloglogK（loglogK要素にログオン）に取り、K回繰り返すので、2,3のために使用される時間は、O（K * logloglogK）である

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. 

。 4多くの場合、O（loglogK）時間を使用して、値を持つすべてのノードを処理します。 5は、カウントソートと同様にO（K）時間を要します。したがって、合計時間はO（nlogloglogK）にする必要があります。

私は本当に眠くて、私がまっすぐ考えていることを保証することができないので、どんな質問も歓迎されます。

Answer 2

あなたはその後、一緒に合計でO(n)の原価計算、各区間をマージO(n/k * k) = O(n)

の総コストのために、それぞれについてO(k) 原価計算、各区間にcounting sortまたはbucket sortを使用することができます。あなたのアルゴリズムはO(n) + O(n) = O(n)アルゴリズムになります。

注：並列処理を利用できる場合は、すべての間隔を並行してソートして、合計コストをO(k)にすることができます。あなたのアルゴリズムはまだO(n)（マージのため）ですが、それはより小さい一定の要因を持っています。