6
票
Accepted
ヒープデータ構造について
回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。
この問題は二分ヒープを対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8...となりますが、最後の段は2の累乗になっているとは限りません。また"at most"はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。
ある関数f(k)...
2
票
ヒープデータ構造について
他の回答者さんがおっしゃってるように、数学的帰納法を使っています。
文章の流れとしては(付番は本文のものとは無関係です)
basis = 高さ0の場合の証明
高さ0のノードの個数<=葉の数より、葉の数<=ceil(n/2)を証明すれば十分
葉の数=ceil(n/2)の証明 (これが原文の大部分を占めています)
inductive step = 高さh-1での成立を仮定して、...
1
票
ヒープデータ構造について
なぜh=0が正しいからの証明から始まるのか
英語も数学も苦手なので途中は一切見ていないのですが、最後の式をみる限り数学的帰納法で証明しているからでしょう。
違和感があるのならh=1から始めても良いかと(h=0と比べると面倒になるのではないかと思いますが)。
また#は何をさしているのか
コメントで別の方が書かれている通りだと思います。
もしもっとわかりやすい証明があれば、...
Only top scored, non community-wiki answers of a minimum length are eligible
関連するタグ
ヒープ × 4アルゴリズム × 2
java × 1
android-studio × 1
データ構造 × 1
メモリ管理 × 1
スタック × 1
android-asynctask × 1
圧縮 × 1