algorithm - ソートアルゴリズム境界証明

Question

このスライドに基づく: http://oi48.tinypic.com/27xmg47.jpg

Q1>なぜN!異なる順序=>で少なくともN!葉を残すのですか?

Q2＞なぜ#leaves >= N!？

2^h >= #leaves の理由は、2^h が完全な二分木の葉の数を表し、#leave がほとんどの場合、不完全な二分木に由来するためです。

Answer 1

N!さまざまな注文があります。アルゴリズムは、どの順序が存在するかを正確に判断する必要があるため、決定木には少なくともN!葉が必要です。そうしないと、すべての可能な順序を区別することができなくなります。