Θ（n）で実行されるアルゴリズムの検索への提案？

A [0..n - 1]を異なる整数の配列とする。 Aのランクkを持つ整数は、Aの整数のうちk番目に大きい整数です。Aのメジアンは、ランクb（n - 1）/ 2cのAの整数です。どのようにアルゴリズムが見えるかもしれません、a kはΘ（n）時間でAの階数kを持つ整数を見つけるのですか？Θ（n）で実行されるアルゴリズムの検索への提案？

出典

2017-02-15 hanko

「b」と「c」とは何ですか？ – Max

おそらくクイックソートのパーティション機能が必要です。 – IVlad

検索するアルゴリズムは、QuickSelectと呼ばれています。これは無作為アルゴリズムであり、（n）時間で、n要素で構成される配列上で動作します。

A worse-case O(n) algorithmも存在しますが、それは理論的な関心事です。

出典

2017-02-15 17:05:29

Θ（n）からΘ（K * log（K））までの時間を妥協できれば - 「K」はKの最大整数を表します。 MaxHeapソートの様子を見てください。「K」が小さいときはΘ（n）に近くなりますが、中央値を扱うときは確かに大きくなります。

出典

2017-02-15 17:00:17

Θ（n）で実行されるアルゴリズムの検索への提案？

答えて

関連する問題