スタック | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第５章
トップページ – アルゴリズムとデータ構造編 この章の概要 この章の概要です。 スタック 配列による実装 連結リストによる実装 まとめ 練習問題 参考リンク 更新履歴 この章では、スタックというデータ構造を説明します。 スタックは非常に重要なデータ構造です。たとえ、自分でスタックを実装することがないとしても、色々な場面でその考え方が登場するので、確実に理解しておきましょう。 スタックは、データの入れ方と取り出し方に特徴があります。スタックは、一番最後に格納したデータしか取り出せません。このような特徴を、後入れ先出しだとか、LIFO (Last In First Out)と呼びます。 後入れ先出しのイメージとして、机の上に積み重ねた本がよく使われます。本をどんどん積んでいくとすれば、上へ上へ重ねていくことになるでしょう。逆に、積み重なった本を手に取るとすれば、一番上にある本から順番に取ります
計算量 | Programming Place Plus アルゴリズムとデータ構造編【導入】 第１章
計算量を用いることで、O(n) のアルゴリズムでは、データの個数n が 2倍になれば、処理時間も 2倍になるであろうという予測が立ちます。ここで n がいくつなのかも、処理時間が何秒なのかもまったく登場しないことがポイントです。特定の環境に依存せずに、アルゴリズムの性能が評価できるというわけです。 この表で上の方にあるほど、計算量が小さい、効率的なアルゴリズムです。しかし、現実的には必ずしも、効率的なアルゴリズムほど高速であるとはいえないことに注意が必要です。 まず、データの個数を表す n は、それなりの大きさがあることを前提としています。小さなデータ列を対象とすると、O(n) よりも O(n log n) の方が高速である可能性もあります。しかし、データ列が大きくなっていけば、歴然とした差が出てきます。 たとえば、n = 10 程度なら、O(n2) のアルゴリズムを使っても問題ないでしょ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
