1

中央値を計算すると、入力配列を 5 つのサブグループに分割して再帰的に解くと、O(n) の複雑さが得られますが、配列を 3 つに分割すると、O(n ) 複雑さ。

それを証明する方法を知っている人はいますか？

4

2 に答える 2

2

それはなるだろうnlg(n)。
再帰ツリー を描いてみてください。各レベルの合計コストは n に等しく、このツリーの深さは ですlg(n)。
注 : 実際には深さはlog(n)底 3 とlog(n)底 3/2 の間にありますが、すべての底の対数の順序が同じであるため、単に と見なすことができlg(n)ます。

于 2013-09-25T06:50:50.673 に答える