次のタグが付いている話題の回答:

6
Accepted

ヒープデータ構造について

回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。 この問題は二分ヒープを対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8...となりますが、最後の段は2の累乗になっているとは限りません。また"at most"はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。 ある関数f(k)...
Kenji Noguchi's user avatar
2

ヒープデータ構造について

他の回答者さんがおっしゃってるように、数学的帰納法を使っています。 文章の流れとしては(付番は本文のものとは無関係です) basis = 高さ0の場合の証明 高さ0のノードの個数<=葉の数より、葉の数<=ceil(n/2)を証明すれば十分 葉の数=ceil(n/2)の証明 (これが原文の大部分を占めています) inductive step = 高さh-1での成立を仮定して、...
letrec's user avatar
  • 3,160
1

ヒープデータ構造について

なぜh=0が正しいからの証明から始まるのか 英語も数学も苦手なので途中は一切見ていないのですが、最後の式をみる限り数学的帰納法で証明しているからでしょう。 違和感があるのならh=1から始めても良いかと(h=0と比べると面倒になるのではないかと思いますが)。 また#は何をさしているのか コメントで別の方が書かれている通りだと思います。 もしもっとわかりやすい証明があれば、...
DEWA Kazuyuki - 出羽和之's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible