指数時間･････････････････････････････････････････････････････････････････････････････････････ 39

Contents

最良な場合 対 最悪な場合の計算量･･･････････････････････････････････････････････ 40
領域計算量･･････････････････････････････････････････････････････････････････････････････････ 41
どうして重要なのか？････････････････････････････････････････････････････････････････････ 42
用語集････････････････････････････････････････････････････････････････････････････････････････ 43
チャレンジ･･･････････････････････････････････････････････････････････････････････････････････ 44

第

第

1
0

部

章

アルゴリズム入門････････････････････････････････････････････････････････････11

第

2

章

再帰･･･････････････････････････････････････････････････････････････････････････････････････････ 45
再帰をいつ使うのか･････････････････････････････････････････････････････････････････････ 51
用語集････････････････････････････････････････････････････････････････････････････････････････ 52

イントロダクション･･･････････････････････････････････････････････････････････････････ 13

チャレンジ･･･････････････････････････････････････････････････････････････････････････････････ 52

この本で学ぶこと･････････････････････････････････････････････････････････････････････････ 15
対象読者は誰？･････････････････････････････････････････････････････････････････････････････ 17
独学プログラマーの成功例････････････････････････････････････････････････････････････ 18
Matt Munsonさん･････････････････････････････････････････････････････････････････････ 18

第Tianni Myersさん･･････････････････････････････････････････････････････････････････････ 20

3章

線形探索･････････････････････････････････････････････････････････････････････････････････････ 54
線形探索をいつ使うのか･･･････････････････････････････････････････････････････････････ 55

さあ、はじめよう･････････････････････････････････････････････････････････････････････････ 21
Pythonのインストール･･････････････････････････････････････････････････････････････････ 22

二分探索･････････････････････････････････････････････････････････････････････････････････････ 57

チャレンジ･･･････････････････････････････････････････････････････････････････････････････････ 23

文字の探索･･････････････････････････････････････････････････････････････････････････････････ 64

二分探索をいつ使うのか･･･････････････････････････････････････････････････････････････ 61

困ったときは？･･････････････････････････････････････････････････････････････････････････････ 22

用語集････････････････････････････････････････････････････････････････････････････････････････ 68

断固として継続しよう･･･････････････････････････････････････････････････････････････････ 23

第

1

章

探索アルゴリズム･ ････････････････････････････････････････････････････････････････････ 53

チャレンジ･･･････････････････････････････････････････････････････････････････････････････････ 69

アルゴリズムとは何か？････････････････････････････････････････････････････････････ 25
アルゴリズムを分析する････････････････････････････････････････････････････････････････ 26
定数時間･････････････････････････････････････････････････････････････････････････････････････ 32
対数時間･････････････････････････････････････････････････････････････････････････････････････ 33
線形時間･････････････････････････････････････････････････････････････････････････････････････ 34
対数線形時間･･･････････････････････････････････････････････････････････････････････････････ 35
多項式時間（二乗）･･････････････････････････････････････････････････････････････････････ 36
多項式時間（三乗）･･････････････････････････････････････････････････････････････････････ 38

4004-010_Computer_KRM_03-2.indd 4-5

第

4

章

ソートアルゴリズム･･･････････････････････････････････････････････････････････････････ 71
バブルソート････････････････････････････････････････････････････････････････････････････････ 72
バブルソートをいつ使うのか･ ････････････････････････････････････････････････････････ 78
挿入ソート･･･････････････････････････････････････････････････････････････････････････････････ 80
挿入ソートをいつ使うのか･････････････････････････････････････････････････････････････ 85
マージソート････････････････････････････････････････････････････････････････････････････････ 85
マージソートをいつ使うのか･･････････････････････････････････････････････････････････ 96

52022/08/02 9:57

Pythonにおけるソートアルゴリズム････････････････････････････････････････････････ 97
用語集････････････････････････････････････････････････････････････････････････････････････････

チャレンジ

第

5

章

･････････････････････････････････････････････････････････････････････････････････

第

2

部

データ構造････････････････････････････････････････････････････････････････････････ 141

第

8

章

データ構造とは何か？･････････････････････････････････････････････････････････････ 143

99

100
用語集･･････････････････････････････････････････････････････････････････････････････････････ 147

文字列のアルゴリズム････････････････････････････････････････････････････････････ 101

チャレンジ･････････････････････････････････････････････････････････････････････････････････ 147

アナグラムの検出･･･････････････････････････････････････････････････････････････････････ 101
回文の検出････････････････････････････････････････････････････････････････････････････････ 103
最後の数字････････････････････････････････････････････････････････････････････････････････ 104

第

9

章

配列･････････････････････････････････････････････････････････････････････････････････････････ 149･････････････････････････････････････････････････････････････････････････････

シーザー暗号

106･･････････････････････････････････････････････････････････････････････････････････････

用語集

111

配列を作成する･･････････････････････････････････････････････････････････････････････････ 155

111

ゼロを移動する･･････････････････････････････････････････････････････････････････････････ 156

チャレンジ･････････････････････････････････････････････････････････････････････････････････

配列のパフォーマンス･････････････････････････････････････････････････････････････････ 152

2つのリストを統合する･･･････････････････････････････････････････････････････････････ 161
第6章

リスト内の重複を見つける･･･････････････････････････････････････････････････････････ 162

数学･････････････････････････････････････････････････････････････････････････････････････････ 113

2つのリストの交差を探す････････････････････････････････････････････････････････････ 166

2進法････････････････････････････････････････････････････････････････････････････････････････ 113

用語集･･････････････････････････････････････････････････････････････････････････････････････ 169

ビット演算子･･････････････････････････････････････････････････････････････････････････････ 118

チャレンジ･････････････････････････････････････････････････････････････････････････････････ 170

FizzBuzz問題･････････････････････････････････････････････････････････････････････････････ 124
最大公約数････････････････････････････････････････････････････････････････････････････････ 128
ユークリッドの互除法･･････････････････････････････････････････････････････････････････ 132
素数･･････････････････････････････････････････････････････････････････････････････････････････

用語集･･････････････････････････････････････････････････････････････････････････････････････

134
138

チャレンジ･････････････････････････････････････････････････････････････････････････････････ 138

第

10

章

連結リスト･･･････････････････････････････････････････････････････････････････････････････ 171
連結リストのパフォーマンス･････････････････････････････････････････････････････････ 174
連結リストを作成する･････････････････････････････････････････････････････････････････ 176
連結リストを探索する･････････････････････････････････････････････････････････････････ 180
連結リストからノードを削除する･ ･････････････････････････････････････････････････ 182

第

7

章

独学伝：マーガレット・ハミルトン･･･････････････････････････････････････ 139

連結リストを逆順にする･･････････････････････････････････････････････････････････････ 184
連結リストの循環を見つける････････････････････････････････････････････････････････ 186
用語集･･････････････････････････････････････････････････････････････････････････････････････ 189
チャレンジ･････････････････････････････････････････････････････････････････････････････････ 190

6004-010_Computer_KRM_03-2.indd 6-7

72022/08/02 9:57

第

11

章

スタック･･･････････････････････････････････････････････････････････････････････････････････ 191

深さ優先走査･････････････････････････････････････････････････････････････････････････････ 253

スタックを作成する････････････････････････････････････････････････････････････････････ 194

用語集･･････････････････････････････････････････････････････････････････････････････････････ 259

二分木を反転する･･････････････････････････････････････････････････････････････････････ 257

スタックをいつ使うのか･･････････････････････････････････････････････････････････････ 192

チャレンジ･････････････････････････････････････････････････････････････････････････････････ 260

スタックを使って文字を反転させる･ ･････････････････････････････････････････････ 200
最小値を保持するスタック･･･････････････････････････････････････････････････････････ 202
括弧用のスタック･･･････････････････････････････････････････････････････････････････････ 206
用語集･･････････････････････････････････････････････････････････････････････････････････････ 209

第チャレンジ･････････････････････････････････････････････････････････････････････････････････ 209

15

章

二分ヒープ･･････････････････････････････････････････････････････････････････････････････ 261
二分ヒープをいつ使うのか･･････････････････････････････････････････････････････････ 267

ヒープを作成する･･･････････････････････････････････････････････････････････････････････ 267
第

12

章

最小の費用でロープをつなぐ･･･････････････････････････････････････････････････････ 272

キュー･･････････････････････････････････････････････････････････････････････････････････････ 211

用語集･･････････････････････････････････････････････････････････････････････････････････････ 274
チャレンジ･････････････････････････････････････････････････････････････････････････････････ 274

キューをいつ使うのか･････････････････････････････････････････････････････････････････ 212
キューを作成する･･･････････････････････････････････････････････････････････････････････ 214
Python組み込みのQueueクラス･････････････････････････････････････････････････ 220
2つのスタックを使ったキューを作成する･･････････････････････････････････････ 222

第用語集･･････････････････････････････････････････････････････････････････････････････････････ 224

16章

グラフ･･････････････････････････････････････････････････････････････････････････････････････ 275
グラフをいつ使うのか･････････････････････････････････････････････････････････････････ 281

チャレンジ･････････････････････････････････････････････････････････････････････････････････ 224

グラフを作成する･･･････････････････････････････････････････････････････････････････････ 282
ダイクストラ法･･･････････････････････････････････････････････････････････････････････････ 286

第

13

章

用語集･･････････････････････････････････････････････････････････････････････････････････････ 296

ハッシュテーブル････････････････････････････････････････････････････････････････････ 225

チャレンジ･････････････････････････････････････････････････････････････････････････････････ 297

ハッシュテーブルをいつ使うのか･･････････････････････････････････････････････････ 230
文字列内の文字の出現回数･････････････････････････････････････････････････････････ 231
2つの整数の和･･･････････････････････････････････････････････････････････････････････････ 234

第

17

章

独学伝：イーロン・マスク････････････････････････････････････････････････････ 299

第

18

章

次のステップ･･･････････････････････････････････････････････････････････････････････････ 303

用語集･･････････････････････････････････････････････････････････････････････････････････････ 237
チャレンジ･････････････････････････････････････････････････････････････････････････････････ 238

第

14

章

二分木

次に何をする？･･･････････････････････････････････････････････････････････････････････････ 303

239

フリーランスのハシゴを登る････････････････････････････････････････････････････････ 304

木構造をいつ使うのか････････････････････････････････････････････････････････････････ 243

採用面接に進む方法･･･････････････････････････････････････････････････････････････････ 305

二分木を作成する･･････････････････････････････････････････････････････････････････････ 247

技術面接の準備･････････････････････････････････････････････････････････････････････････ 306

幅優先走査････････････････････････････････････････････････････････････････････････････････ 250

その他の情報･････････････････････････････････････････････････････････････････････････････ 307･････････････････････････････････････････････････････････････････････････････････････

8004-010_Computer_KRM_03-2.indd 8-992022/08/02 9:57

最後に･･･････････････････････････････････････････････････････････････････････････････････････ 307

第

3

部

もっと学ぼう････････････････････････････････････････････････････････････････････ 309

1 アルゴリズムへの理解を深めるために─ハッシュテーブル─
補章 2 アルゴリズムへの理解を深めるために─ダイクストラ法─補章 3 継続して学ぶために
補章････････････

311･ ･････････････

321････････････････････････････････････････････････････････････････････

333

日本語版に寄せて･ ･････････････････････････････････････････････････････････････････････ 338
日本語版あとがき･･･････････････････････････････････････････････････････････････････････ 340
索引･･････････････････････････････････････････････････････････････････････････････････････････ 344

訳注コラム
日本語の文字コードとエンコード例････････････66

探索効率と準備コスト･･･････････････････････････67

マージソートの後半部分････････････････････････86

Pythonの多次元配列･･････････････････････････ 151
連結リストの要素挿入･････････････････････････ 173
in 演算子による、より自然な使い方･･･････ 182

例外処理をうまく扱う･････････････････････････ 188
文字列の最大ヒープをタプルで作る･････････ 271

・本書に登場するウェブページのURLは、本書編集時点（2022年7月）のものです。
・本書掲載のコードで1行に入り切れないものは、行末で改行したうえで、行番号分
字下げして掲載しています。
・本書掲載のコードは以下からダウンロードいただけます。補足情報等も以下からご覧いただけます。
https://bookplus.nikkei.com/atcl/catalog/22/07/19/00285/

10004-010_Computer_KRM_03-2.indd 102022/08/02 9:57