1

このリンクでわかるように：http：//en.wikipedia.org/wiki/D-ary_heap#Applications ウィキペディアでは、dの最適な選択はd = m / nであると述べています（これにより、合計時間計算量がO（m logm / nn））

この推測は薄い空気から引き出されたように私には思えます。これが本当に最適なdであることを証明する（または説明する）簡単な方法はありますか？

前もって感謝します

4

1 に答える 1

3

説明自体から、それぞれが必要O(d log(n)/log(d))とする最小の操作をn個削除し、の優先度の操作をm個減らすことができますO(log(n)/log(d))。結合された作業は次のようになり(m*log(n)+n*d*log(n))/log(d)ます。

提案されたd値を入力すると、グローバルな動作は次のようになりO(m*log(n)/log(d))ます。他のdを取ると、項の1つが平均よりも大きくなり、複雑さが増します。

于 2012-12-07T13:16:26.433 に答える