performance - マージソートの再帰ツリーのレベルの総数が lg n + 1 であるのはなぜですか?

Question

ここでの質問はかなり自明だと思いますが、「アルゴリズムの紹介」第3版の37ページを見ていると、図2.5の再帰ツリーのレベルの総数はlg n + 1であると書かれていますが、わかりません+1する必要がある理由。誰かがこの背後にある理論的根拠を説明できますか? ありがとう

Answer 1

ツリーには N 個の葉が含まれている必要があります。レベル h(ルートがレベル 1) の二分木には最大で 2^(h-1) の葉があるため、2^(h-1) >= n、つまり h >= lg(n)+1 であると断言します。 . 同時に、完全な二分木である必要があります。レベル h の完全な二分木には、少なくとも (2^(h-2)+1) の葉があります。つまり、2^(h-2)+1<=n, h<=lg(n-1)+2 です。

n=2^k のとき、k+2>h>=k+1 なので、h=k+1=lg(n)+1 であり、本の場合です。

さらに、n!=2^k のとき、2^k>n>2(k-1) である ak があり、h>=lg(n)+1>k および h< lg(n)+ 2 < k+2、つまり h = k+1 = ceil(lg(n)+1) です。

全体として、k = ceil(lg(n)+1) です。ここで、ceil(lg(n)+1) は、lg(n)+1 より小さくない最小の整数を示します。