アルゴリズム

「アルゴリズム」のキホン

杉浦賢
ソフトバンククリエイティブ

はじめに
登場キャラクターのご紹介

第1章 アルゴリズムとは

  • 001 料理のレシピはアルゴリズムである
  • 002 アルゴリズムは先人の知恵である
  • 003 アルゴリズムを知ることはゲームに強くなるようなもの
  • 004 アルゴリズムには「正当性」と「停止性」がなければならない
  • 005 アルゴリズムにはたくさんの種類がある

COLUMN アルゴリズムの基礎となる構造化プログラミングの考え方

第2章 変数と配列

  • 006 データとはさまざまな情報である
  • 007 すべてのデータには型がある
  • 008 値とは数値や文字などの具体的な表現である
  • 009 変数とは値を入れておく箱である
  • 010 変数は「変数名」という名前で区別される
  • 011 代入分は変数に値を代入する機能をもつ
  • 012 変数から変数への代入とは、変数に格納された値を別の変数に記憶すること
  • 013 変数にもデータ型がある
  • 014 同じデータ型の連続が配列である
  • 015 配列は「配列名」という名前で区別される
  • 016 配列の各要素は要素番号という番号で識別される
  • 017 配列は関連する値を効率よく格納するためのリッカーである
  • 018 2次元配列はホテルの部屋のようなものである
  • 019 配列の各要素は2つの添字によって識別される
  • 020 文字列は文字データの配列である
  • 021 文字列の文字長は、文字長変数もしくは「番兵」により管理される

COLUMN 慣用的に使用される変数名

第3章 データ構造

  • 022 大量のデータを効率よく管理するためのしくみがデータ構造である
  • 023 データ構造にはたくさんの種類がある
  • 024 本を積み上げるようなデータ構造がスタックである
  • 025 レジに順番に並ぶようなデータ構造が待ち行列(キュー)である
  • 026 ひもでつながれたようにデータを管理するのがリストである
  • 027 一方の端からデータをたどっていくのが単方向リストである
  • 028 両端からデータをたどっていけるのが双方向リストである
  • 029 N番目の要素の参照が速いのは配列で、遅いのはリスト構造である
  • 030 データの挿入・削除が速いのはリスト構造で、遅いのは配列である
  • 031 末尾までいったら先頭に戻ってくるのがリングバッファである
  • 032 親1人、子ども2人の構造をしているのが二分木である
  • 033 親ノードの値が常に子ノードの値より大きくならない二分木がヒープである
  • 034 ハッシュテーブルは配列とリストを組み合わせたデータ構造である
  • 035 節点と辺により項目のつながりを図的に表現したのがグラフである

COLUMN BASE 0なのか、BASE 1なのか

第4章 基本的なアルゴリズム

  • 036 1〜Nの合計値を求めるには繰り返し処理を行う
  • 037 数列の値を保持するには配列を使う
  • 038 配列データの合計値を求めるには合計値を加算する変数を用意する
  • 039 配列データの有効な要素数を求めるにはカウンタを用意する
  • 040 配列データの平均は繰り返し処理で合計値と個数を求めて計算する
  • 041 配列データ内の最大値を求めるには、最大値を保持する変数を用意する
  • 042 配列データ内の最小値を求めるには、最長値を保持する変数を用意する
  • 043 配列データの順位をつけるには、順位を格納する別の配列を用意する
  • 044 時刻の大小比較するには、単位を秒にそろえる
  • 045 時刻の差を求めるには、秒単位で差を求めてから時刻表示に戻す
  • 046 2つの変数の値を入れ替えるには、一時的なワーク変数を利用する
  • 047 2つの数値の最大公約数はユークリッド互除法で求める

COLUMN コードやデータはどこにあるのか?

第5章 並び替えと探索

  • 048 並び替え(ソート)とは、対象をある規則に従って並び替えること
  • 049 ソートアルゴリズムにはさまざまな種類がある
  • 050 別配列(バケツ)にデータを格納して並び替えを行う「バケットソート」
  • 051 数値の下の桁から順にバケットソートを繰り返す「基数ソート」
  • 052 最小値(最大値)を選択し、ソートずみデータの末尾と交換する「単純選択法」
  • 053 隣接するデータを交換していく「単純交換法」(バブルソート)
  • 054 ソートずみデータ中で正しい大小関係の位置にデータを挿入する「単純挿入法」
  • 055 データ列を一定間隔のグループに分けて並び替える「シェルソート」
  • 056 複数のソートずみデータ列を合体させる「併合」(マージ)
  • 057 併合(マージ)のアルゴリズムを利用することでソートを行うマージソート
  • 058 基準データとの大小関係でデータ列を2分割する「クイックソート」
  • 059 ヒープ構造を利用して並び替える操作を行う「ヒープソート」
  • 060 探索とは、複数のデータの中〜目的のデータを探しだすこと
  • 061 先頭からしらみつぶしにデータを比較する「線形探索」(リニアサーチ)
  • 062 ソートずみデータ列から高速にデータを探し出せる「二分探索」(バイナリサーチ)
  • 063 与えられた文字列の中で、指定した部分文字列の位置を調べる「文字列探索」
  • 064 不一致文字位置と部分文字列の構成から文字探索を効率化するKPM法
  • 065 部分文字列の末尾から先頭に向かって文字を比較していくBM法

COLUMN リレーショナルデータベースの利用によるソートや探索

第6章 そのほかのアルゴリズム

  • 066 微分を活用することで高次方程式の解を求めるのがニュートン法
  • 067 連立方程式の解を求めるのがガウスの消去法
  • 068 台形の面積の加算により定積分の値を求めるのが台形法
  • 069 最短時間、最短距離などの最適経路を求めるのがグラフによるダイクストラ法
  • 070 自然数nが素数であるか否かを判定する「エラトステネスのふるい」
  • 071 再帰呼びだしを利用してnの階乗を求める

COLUMN アルゴリズムとフローチャート(流れ図)

第7章 アルゴリズムの計算量

  • 072 アルゴリズムの計算量には、時間計算量と領域計算量がある
  • 073 時間計算量は、「演算」「条件比較」「代入処理」などの操作回数で計測する
  • 074 アルゴリズムの計算量は、「O(オー)記法」で表す

COLUMN プログラムの上達法

参考文献
索引