1

最悪の場合、T がアルゴリズムの実行時間である場合、サイズ 3 のブロックで中央値アルゴリズムの中央値を使用すると、次の再帰関係が得られる理由がわかりました。

T(n) = T(2n / 3) + T(n / 3) + O(n)

median-of-medians アルゴリズムに関するウィキペディアの記事では、サイズ 3 のブロックでは、n 個の要素すべてをチェックする必要があるため、実行時間は O(n) ではないと述べています。私はこの説明をよく理解していません.私の宿題では、帰納法でそれを示す必要があると書かれています.

この場合、中央値の中央値に時間 Ω(n log n) がかかることをどのように示しますか?

4

2 に答える 2

-1

T(2n/3) と T(n/3) の小数部分を足すと、T(n) が得られます。次に、マスター定理を使用すると、n^(log_(b)(a)) = n^(log_(1)(1)) = n となります。f(n) = O(n) もあります。したがって、n^(log_(b)(a)) = O(n) = Theta(f(n)) であるため、マスター定理のケース 2 が適用されます。したがって、T(n) = Theta(n^(log_(b)(a)) * log(n)) = Theta(n*log(n)) です。

于 2016-06-07T21:35:12.673 に答える