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

12

ヒープ領域とスタック領域の違いについて教えてください

(一般的な話を書いたら長文になってしまいました。) プログラムが実行時にどうメモリを使うか、については色々なやり方があって、実際に色々試されて来たのですが、その中で定番になったのが、データを寿命によって次のとおり分類する方法です。 プログラムを実行する前からどのくらい必要か決まっていて、実行開始時から終了時まで存在し続けるもの 関数/サブルーチンの実行中のみ必要で、...
  • 4,298
6

ヒープ領域とスタック領域の違いについて教えてください

1つだけ答えてみます スタック領域のデータ構造はどのようなものなのか スタックです
  • 2,593
6
Accepted

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

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

ヒープ領域とスタック領域の違いについて教えてください

ヒープ領域とスタック領域の違いについて教えてください メモリ領域にはテキスト領域、静的領域、ヒープ領域、スタック領域の4つの領域がある。 テキストはプログラム、静的はグローバル変数やstatic変数、スタックは装飾しのないローカル変数、ヒープは動的に確保できる ここでプログラムやグローバル変数は利用する数や処理が確定すれば、プログラム中でサイズが変化することはない、...
  • 171
5
Accepted

ヒープ領域とスタック領域の違いについて教えてください

スタックとヒープの違いを、使い方とデータ構造から説明します。 スタックは手続きの呼び出しで利用されます。手続きが呼び出されると、呼び出された手続きのローカル変数を格納するためのフレームがスタック上に生成されます。手続きからリターンすると、そのフレームも不要になります。メモリ領域の確保と解放のタイミングは、後から呼び出された手続きのフレームほど先に解放されます。 従って、...
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と比べると面倒になるのではないかと思いますが)。 また#は何をさしているのか コメントで別の方が書かれている通りだと思います。 もしもっとわかりやすい証明があれば、...

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