入門データ構造とアルゴリズム

インド工科大学 (IIT) と企業の両方で豊富な経験を持つインド人著者による、実例豊富なデータ構造とアルゴリズムの解説書。伝統的なデータ構造とアルゴリズムのトピックで、基本をしっかり押さえるだけでなく、集合の Union / Find、動的プログラミングや計算量クラスといった話題も盛り込んでいます。圧倒的な情報量でプログラマに必要な知識を網羅。600 弱の練習問題とその解を収録しており、理解度を細かく確認し、知識を着実に身に付けることができます。

『入門データ構造とアルゴリズム』は、データ構造とアルゴリズムの基本を、解説と大量の練習問題の往復で身につけるための解説書です。著者は Narasimha Karumanchi さん、訳者は黒川 利明さんと木下 哲也さんで、オライリー・ジャパンから 2013 年 8 月 24 日に発行されました。原書は Data Structures and Algorithms Made Easy の第 2 版です。版元の紹介文によると、著者はインド工科大学 (IIT) と企業の両方で経験を積んだ人物で、伝統的なトピックの基本に加えて集合の Union/Find、動的プログラミング、計算量クラスまでを扱い、600 弱の練習問題とその解を収録しています。

全 21 章の構成、計算量の解析から計算量クラスまで

1 章「はじめに」は変数やデータ型、抽象データ型 (ADT) の整理から入り、増加率、漸近表記法、O 表記、Ω 表記、Θ 表記、分割統治マスター定理、ならし解析までを扱う、解析の道具立ての章です。2 章で再帰と後戻りを押さえたあと、3 章の連結リストから 4 章スタック、5 章キュー、6 章木、7 章優先度付きキューとヒープ、8 章互いに素な集合 ADT、9 章グラフアルゴリズムと、データ構造を 1 つずつ積み上げます。10 章から 15 章は整列、探索、選択アルゴリズム、記号表、ハッシュ、文字列アルゴリズムで、15 章ではラビン・カープ法、KMP アルゴリズム、ボイヤー・ムーア法、トライ、接尾辞木まで進みます。16 章から 19 章はアルゴリズム設計技法の分類と、貪欲アルゴリズム、分割統治アルゴリズム、動的プログラミングで、20 章が計算量クラス、21 章がビット単位プログラミングなどその他の話題です。多くの章の末尾に「〜の問題」という節が置かれ、解説の直後に演習が続く並びになっています。

計算量の物差しを先に持つことの意味

データ構造の学習でつまずきやすいのは、配列、連結リスト、木、ハッシュ表のどれを選ぶべきかを、感覚ではなく根拠で説明する場面です。根拠になるのは、入力が大きくなったときに処理時間やメモリがどう増えるかという 計算量 の見積もりで、本書が 1 章の大半を漸近的解析と再帰式の解き方に割き、その物差しを持った状態で各データ構造に入る順序になっているのはこのためと読めます。たとえば 14 章には「ハッシュはどのようにして計算量 O (1) を実現するのか?」という節があり、ハッシュテーブル の平均 O (1) という性質を、衝突解消手法の比較と合わせて確かめる流れです。19 章の 動的計画法 は、部分問題の結果を再利用して計算の重複を消す設計手法で、2 章の再帰と 18 章の分割統治を通ってから読むと、なぜ速くなるのかを式の上で追いやすくなります。

練習問題を軸に学びたい人へ、向かない人と選び方

向いているのは、基本情報技術者試験や大学の講義でデータ構造の用語には触れたものの、自分で手を動かして使い分けを身につけたい人や、技術面接やコーディング試験に備えて典型問題を数多く解いておきたい人です。600 弱の練習問題と解が揃っているため、1 章ずつ通読するだけでなく、必要な章の問題だけを拾って解く使い方にも向きます。一方で、プログラミングそのものが初めての人には、1 章から漸近表記と再帰式が並ぶ構成は負担が大きく、先に 1 つの言語で配列やループを書ける状態にしておく必要があります。証明を重視した厳密な教科書を求める人や、図解中心でやさしく概観したい人にも別の本が合います。

2013 年刊の翻訳書で、版元のページには第 1 刷の正誤表が掲載されているので、手元の刷数を確認して照らし合わせておくと安心です。どの種類の本を選ぶか迷ったら、アルゴリズム本ガイド でタイプ別の使い分けを確かめてから決めると選びやすくなります。データ構造ごとに解説と問題がまとまった 1 冊を手元に置き、繰り返し解いて使い分けの判断を身につけたい人にとって、本書は収録量の点で元を取りやすい選択肢です。