アレイサイズN kの同じサイズのグループには

Question

IサイズNの未ソートアレイを有し、IはK-1除数を見つける必要があるので、すべてのサブセットが同じサイズである（のようなアレイがソートされた後） 。

私はk-1 = 3でこの問題を見てきました。私はメジアンの中央値が必要だと思います。これはo（n）です。しかし、私たちはそれを行うべきだと思う。k回o（nk）。
o（n logk）の理由を理解したいと思います。

例：私は配列が未定義であり、その値に従ってk（同じサイズの）サブアレイに分割するk-1の整数であるkの除数を見つけたいと思います。
私が[1, 13, 6, 7, 81, 9, 10, 11]を持っているならば、3 = kデバイダは[1 6, 9 10 13 81]に分割する[7 ,11]であり、各サブセットは2で等しくなります。

Answer 1

分割と征服のアプローチを使用できます。まず、中央値メジアンアルゴリズムを使用して(k-1)/2分周器を見つけます。次に、選択した要素を使用して、リストを2つのサブリストに分割します。残りの分周器を見つけるために各サブリストでアルゴリズムを繰り返します。

最大再帰深度はO(log k)であり、各レベルのすべてのサブリストの合計コストはO(n)であるため、アルゴリズムはO(n log k)です。