12
票
ヒープ領域とスタック領域の違いについて教えてください
(一般的な話を書いたら長文になってしまいました。)
プログラムが実行時にどうメモリを使うか、については色々なやり方があって、実際に色々試されて来たのですが、その中で定番になったのが、データを寿命によって次のとおり分類する方法です。
プログラムを実行する前からどのくらい必要か決まっていて、実行開始時から終了時まで存在し続けるもの
関数/サブルーチンの実行中のみ必要で、...
- 4,298
6
票
6
票
Accepted
ヒープデータ構造について
回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。
この問題は二分ヒープを対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8...となりますが、最後の段は2の累乗になっているとは限りません。また"at most"はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。
ある関数f(k)...
- 4,051
6
票
ヒープ領域とスタック領域の違いについて教えてください
ヒープ領域とスタック領域の違いについて教えてください
メモリ領域にはテキスト領域、静的領域、ヒープ領域、スタック領域の4つの領域がある。
テキストはプログラム、静的はグローバル変数やstatic変数、スタックは装飾しのないローカル変数、ヒープは動的に確保できる
ここでプログラムやグローバル変数は利用する数や処理が確定すれば、プログラム中でサイズが変化することはない、...
- 171
5
票
Accepted
ヒープ領域とスタック領域の違いについて教えてください
スタックとヒープの違いを、使い方とデータ構造から説明します。
スタックは手続きの呼び出しで利用されます。手続きが呼び出されると、呼び出された手続きのローカル変数を格納するためのフレームがスタック上に生成されます。手続きからリターンすると、そのフレームも不要になります。メモリ領域の確保と解放のタイミングは、後から呼び出された手続きのフレームほど先に解放されます。
従って、...
- 183
5
票
ヒープ領域とスタック領域の違いについて教えてください
質問がズレてきてしまっているのかもしれないので、最初の質問文「ヒープ領域とスタック領域の違いについて教えてください」に答えてみようと思います。
メモリ領域は元々は1つですがそれでは扱い辛いため、任意サイズ・ブロックに切り出し、使用・未使用を管理することで便利になります。この管理自体や切り出されたブロックのことをheapと呼びます。このメモリブロックをどのように使うかは利用者側の自由です。
...
- 4.1万
2
票
ヒープデータ構造について
他の回答者さんがおっしゃってるように、数学的帰納法を使っています。
文章の流れとしては(付番は本文のものとは無関係です)
basis = 高さ0の場合の証明
高さ0のノードの個数<=葉の数より、葉の数<=ceil(n/2)を証明すれば十分
葉の数=ceil(n/2)の証明 (これが原文の大部分を占めています)
inductive step = 高さh-1での成立を仮定して、...
- 3,140
1
票
ヒープデータ構造について
なぜh=0が正しいからの証明から始まるのか
英語も数学も苦手なので途中は一切見ていないのですが、最後の式をみる限り数学的帰納法で証明しているからでしょう。
違和感があるのならh=1から始めても良いかと(h=0と比べると面倒になるのではないかと思いますが)。
また#は何をさしているのか
コメントで別の方が書かれている通りだと思います。
もしもっとわかりやすい証明があれば、...
- 1.1万
Only top scored, non community-wiki answers of a minimum length are eligible