# データ構造：不変条件と操作コストを説明する — 学習ワークシート

[学習ガイド](https://unireadinglist.com/ja/guides/data-structures/)

[科目・テーマ: データ構造](https://unireadinglist.com/ja/subjects/computer-science/#course-data-structures)

出典確認日: 2026-11-04

学習順路・例題の編集責任：University Reading List編集プロジェクト。

ループ、関数、配列、参照を学んだ後の第2科目向け。Morinは数学的解析、GoodrichはJavaのクラスとジェネリクス、Wengrowは具体的な手順の計数に向きます。以下は創作アルゴリズムの計数で、組込みリストの実測ではありません。

## 出発点を選ぶ

- [ ] 無料で厳密に学ぶ
  Morin著者サイトのJavaまたは擬似コード版を使い、総和・対数・初歩の確率を復習して実装と証明を並べます。

- [ ] Javaの実装課題がある
  Goodrichで抽象データ型とAPIを学び、教材と課題のインターフェースを照合します。

- [ ] コードは書けるがBig Oが難しい
  Wengrowの図と計数から始め、償却の根拠をMorinで確認します。一例を全系列の証明にはしません。

## 三冊を比較する

### Open Data Structures: An Introduction（オープンデータ構造入門）

Pat Morin · 2013
無料の解析主教材

選ぶ場面: ループと総和を読め、表現から計算量を導きたい。
別の教材が適する場面: 最初のプログラミングや添字と値の区別がまだ必要。
読む範囲: 著者のJava／擬似コード版で配列リスト、連結リスト、ハッシュ表。2013年紙版では第2、3、5章。
限界と注意点: 著者のオンライン本文・コードのAttribution条件と、AU Press PDFの非営利・改変禁止条件は別です。

#### 選ぶ前に試す

n≤容量を述べ、12回の追加で移す全要素を数える。
確認すること: 添字が有効な理由と、拡張が一回の費用を増やす理由の両方を説明する。

自分のメモ:

________________________________

ISBN: 9781927356388

[公式の無料教材](https://opendatastructures.org/)

[書誌情報と入手方法](https://unireadinglist.com/ja/subjects/computer-science/open-data-structures/)

### Data Structures and Algorithms in Java（Javaによるデータ構造とアルゴリズム）

Michael T. Goodrich; Roberto Tamassia; Michael H. Goldwasser · 6 · 2014
Java実装主教材

選ぶ場面: クラスと事前条件を設計し、抽象データ型を実装したい。
別の教材が適する場面: 参照・例外・ジェネリクスを学ばず言語中立の近道だけを求める。
読む範囲: 2014年第6版紙版ISBN 9781118771334。配列／リスト、スタック／キュー、解析を題名で選ぶ。
限界と注意点: 学生用コードの公開は商用本文の無料公開ではありません。後の電子版は別の識別子です。

#### 選ぶ前に試す

キューのAPIを書き、循環配列で空状態と追加・取り出しを追う。
確認すること: FIFOという動作と折返しという表現を分け、空と満杯を識別できる。

自分のメモ:

________________________________

ISBN: 9781118771334

[書誌情報と入手方法](https://unireadinglist.com/ja/subjects/computer-science/data-structures-and-algorithms-in-java/)

### A Common-Sense Guide to Data Structures and Algorithms: Level Up Your Core Programming Skills（常識で分かるデータ構造とアルゴリズム）

Jay Wengrow · 2 · 2020
直感的な計数の補助

選ぶ場面: 基本的にコードを書け、記号の前に具体的な手順が欲しい。
別の教材が適する場面: 図だけで最悪時や確率的な界を証明したい。
読む範囲: 2020年第2版ISBN 9781680507225。構造の重要性、Big O、スタック／キュー、ノード構造。
限界と注意点: JavaScript・Python・Rubyの例のライブラリ費用を手作りモデルと同一視しません。公開抜粋と全編は別です。

#### 選ぶ前に試す

配列の先頭削除と、既知の連結リスト先頭参照を使う操作を比較する。
確認すること: シフトとリンク変更を分け、参照がなければノード探索も数える。

自分のメモ:

________________________________

ISBN: 9781680507225

[書誌情報と入手方法](https://unireadinglist.com/ja/subjects/computer-science/common-sense-guide-data-structures-algorithms-wengrow/)

## 準備を確認する

### 不変条件とは？

自分のメモ:

________________________________

### 償却とは？

自分のメモ:

________________________________

### 何を数える？

自分のメモ:

________________________________

## 六つのステップで学ぶ

- [ ] 動作を定める

読む範囲: 選んだリスト／キューの導入。

取り組む課題: 操作、空・満杯時、利用者が観察できる結果を書く。

確認すること: APIは配列か連結構造かを決めない。

自分のメモ:

________________________________

- [ ] 表現を描く

読む範囲: Morinの配列リストまたはGoodrichの該当項目。

取り組む課題: 拡張前後のn、容量、使用スロット、挿入位置を描く。

確認すること: 旧値は順に一度ずつ現れ、新値が末尾に入る。

自分のメモ:

________________________________

- [ ] 系列を数える

読む範囲: Wengrowの計数とMorinの拡張論。

取り組む課題: 12行の台帳に容量、コピー、累計書込みを記す。

確認すること: 一回の最悪費用と系列全体を分ける。

自分のメモ:

________________________________

- [ ] 成長規則を変える

読む範囲: 同じ配列の議論。

取り組む課題: 倍増を容量+2へ替え、台帳を再作成。

確認すること: 等比和と等差和の違いを説明する。

自分のメモ:

________________________________

- [ ] 縮小の間隔を調べる

読む範囲: 拡張・縮小の議論と変式。

取り組む課題: 正確な二つのしきい値で4組の追加／削除を追う。

確認すること: 間隔はこの振動を防ぐが、コピー自体をなくさない。

自分のメモ:

________________________________

- [ ] 選択を弁護する

読む範囲: リストとキューの選読。

取り組む課題: 添字参照と先頭削除の負荷を別々に推奨する。

確認すること: 参照の有無、費用、不変条件、除外した費用を示す。

自分のメモ:

________________________________

## 解答付きの例題: 独自の追加台帳：平均が小さくても一回は高い

空の配列の初期容量は2。満杯で追加するときだけ倍増し、12要素を追加します。書込み総数と最終容量を求め、容量を2ずつ増やす案と比較してください。

前提: 値は0…n−1。拡張では旧n値を全て移し、新値を一回書きます。初期確保、読出し、ゼロ化、削除消去は除外し、途中で削除しません。

自分のメモ:

________________________________

## 前提を変えて考える: しきい値を変更：縮小が拡張を取り消す

初期サイズ8・容量8とし、構築は数えません。追加一回・pop一回を4組。満杯なら倍増、pop後Hはn≤容量/2で半減、Qはn≤容量/4で半減。最小容量2。追加と移動の書込みだけ数えます。

自分のメモ:

________________________________

## 次に進む前に

- 操作後に不変条件を回復できる。
- 追加台帳と二つの縮小経路を再計算できる。
- 負荷を指定して構造を選び、計数を実測時間と区別できる。

## 解答と解釈

### 不変条件とは？

例えば0≤n≤容量で、有効値が0…n−1を占め、各操作前後に成立する性質です。実行時間ではありません。

### 償却とは？

系列の総費用に界を与えて操作へ分担させる方法です。全操作が速い、入力がランダム、という意味ではありません。

### 何を数える？

新要素の書込みと旧要素の移動を各1。確保、読出し、ゼロ初期化、解放、削除スロットの消去は数えません。

### 独自の追加台帳：平均が小さくても一回は高い

1. 倍増のコピーは追加3、5、9回目の2、4、8値、計14。新規12回を加えて26書込み、サイズ12・容量16です。
2. 9回目だけでは8移動+1新規=9書込み。系列平均26/12=13/6は各回の上限ではありません。
3. +2では2+4+6+8+10=30コピー、新規込み42書込み。最終サイズと容量は12。空きが少ない分、コピーが増えました。
4. 倍増のコピーは等比和、固定増分は等差和です。このモデルでは総移動量が線形と二次に分かれますが、実測速度の順位ではありません。

倍増は26書込み・容量16、+2は42書込み・容量12。倍増でも9回目は9書込み。

結果を検証する: 全拡張を列挙。8→16では新旧を一時併存させるので確保スロットは24。最終の空き容量とは別です。

### 前提を変えて考える: しきい値を変更：縮小が拡張を取り消す

1. Hは各追加で8を移して容量16、pop後n=8ですぐ容量8へ縮小し8を移します。4組で64コピー+4追加=68。
2. Qは最初の8コピーのみ。pop後n=8・容量16は四分の一の4を超え、縮小せず8+4=12。
3. 最終サイズは両方8、容量はHが8、Qが16。Qは保持空間と引換えにこの往復移動を避けます。削除スロットの消去は数えません。

同じ8操作でHは68、Qは12書込み。保持容量は異なります。

結果を検証する: 8操作後のサイズ／容量を順に記す。除外した初期構築や消去コストを足さない。

## よくある誤り

### 最悪時と償却の混同

一回の高費用は一回ごとの定数界を否定し、定数償却界は否定しません。

### 探索の省略

既知ノードのリンク更新と、そのノードの探索は別の費用です。

### 計数モデルのすり替え

実際の確保、キャッシュ、保持メモリーは重要ですが、この問題には実測値がありません。

## 出典と版の確認

- [Morin: free online editions, source code and licence](https://opendatastructures.org/)
  無料版で実装と解析を組み合わせますが、プログラミングと数学記号の準備が必要です。

- [AU Press: selected 2013 print identity and contents](https://www.aupress.ca/books/120226-open-data-structures/)
  2013年紙版の目次・識別子・許諾をオンライン版から区別します。

- [Wiley: Java sixth edition and product formats](https://www.wiley.com/en-br/data-structures-and-algorithms-in-java-6th-edition-p-9781118771334)
  第6版紙版のJavaとAPIの重点が実装ルートを支えます。

- [Pragmatic Bookshelf: second-edition contents and practice](https://pragprog.com/titles/jwdsal2/a-common-sense-guide-to-data-structures-and-algorithms-second-edition/)
  第2版の図と計数を入口にします。数値台帳は本ガイド独自です。

提案する学習活動であり、公式の課題や全巻通読の主張ではありません。

[編集と選定の方法](https://unireadinglist.com/ja/editorial/)