第1章 アルゴリズムとは何か

投稿者: | 2022-11-16
0件のコメント
  • 参考文献『独学コンピューターサイエンティスト』
あなたは何でもできるし、何にでもなれます。挑戦することをためらわないでください。たとえ何もかもうまくいってないときだとしても。

プログラミングのような新しいスキルを身に付けるうえで一番難しいのは、学ぶ内容の難しさではなく、学び続けることです。「鎖を切らすな」です。

目次

用語集

アルゴリズム

  • 問題を解決する一連の手順、要は「効率的な計算方法」
  • そのアルゴリズムを選択した理由を説明できることは重要
  • アルゴリズムとは、入力に基づいて出力を生成する「明確で、実効で、有限で、正確な処理」をさす

実行時間

  • アルゴリズムをコンピューターが実行するのにかかる時間
import time

start = time.time()
for i in range(1, 100):
  print(i)
end = time.time()
print(end - start)

>> 0.0005009174346923828

問題の大きさ

  • 方程式のアルゴリズムのステップ数を表現するための変数n。変化する値 n のこと。
  • 知りたいことは n が大きくなるにつれてアルゴリズムのパフォーマンスがどうなるか
  • 正確なステップ数ではなく、n が大きくなるときにステップ数がどうなるか、が大事
def print_it(n):
  # ループ1
  for i in range(n):
    print(i)
  # ループ2
  for i in range(n):
    print(n)
    for j in range(n):
      print(j)
      for h in range(n):
        print(h)

上記の例だと、
ループ1で n回のステップ数
ループ2で n回 × n回 × n回 = n3
合計 T(n) = n + n3　（ここではtimeのTを算出する方程式）
この方程式では、nが10なら約103（1000）ステップ、nが1000だと約10003（10億）ステップ…になる

O記法（オーダー記法）

  • nのサイズの増加によって、アルゴリズムの時間や必要な領域がどのように増加するかを表す数学的表記
  • 上記の例でわかるとおり、n が大きくなるにつれて、もっとも増える部分が重要になる

オーダー

  • 桁が何倍大きいか小さいかを数学的に表す仕組み
  • オーダー関数では、方程式 T(n) のうちステップ数がもっとも多い部分だけを使い、その他の部分は無視する
  • その他の部分は、無視できるほど影響がないから。上記例でいうと、n + n3 の 前半 n は無視し、n3だけに着目する
  • 方程式 T(n) のステップ数がもっとも多い部分がアルゴリズムのオーダーになる

時間計算量

  • nがおおきくなったときに、アルゴリズムを完了するのに必要な最大のステップ数

なぜ重要なのか？

  • アルゴリズムを最適化するためには、オーダーの違いを理解する必要がある
  • アルゴリズムを改善する際は、まずオーダーの変化に注目するべき
  • 2つのforループを使ったO(n2)のアルゴリズムがあるとする。このとき、ループの中で起こることを最適化するよりも、アルゴリズムを書き直し、forループを2つ使わないようにして、オーダーを小さくすることを最優先すべき
  • 入れ子にしていない2つのforループを書いてこの問題を解決したら、アルゴリズムはO(n)になり、そのパフォーマンスには大きな違いが生じる

以下は、O記法のオーダーを表す代表的な種類（青文字）。もっとも効率的なものから並べている

定数時間

  • 問題のサイズにかかわらず、同じステップ数で実行されるアルゴリズムの時間計算量
  • T(n) = 1

対数時間

  • 入力サイズの対数に比例した実行時間で実行されるアルゴリズムの時間計算量
  • O(log n)（O記法）

線形時間

  • 問題のサイズと同じ比率の実行時間で実行されるアルゴリズムの時間計算量
  • O(n)

対数線形時間

  • 対数時間計算量と線形時間計算量を組み合わせた（かけ算した）実行時間で実行されるアルゴリズムの時間計算量
  • O(n log n)

多項式時間（二乗）

  • アルゴリズムのパフォーマンスが問題のサイズの二乗に正比例する場合の、アルゴリズムの時間計算量
  • O(n2)

多項式時間（三乗）

  • アルゴリズムのパフォーマンスが問題のサイズの三乗に正比例する場合の、アルゴリズムの時間計算量
  • O(n3)

多項式時間

  • アルゴリズムが O(na) として増える場合の時間計算量。a=2の場合は多項式時間（二乗）になる。

指数時間

  • アルゴリズムが c の n 乗のステップ数を含む場合の時間計算量（最悪！）
  • O(cn) （c:定数）

力まかせ探索アルゴリズム

  • すべての可能な選択肢をテストするタイプの問題解決手順

最良な場合の計算量

  • 想定できる最良のシナリオで実行される場合のアルゴリズムのパフォーマンス

最悪な場合の計算量

  • 想定できる最悪なシナリオで実行される場合のアルゴリズムのパフォーマンス

平均的な場合の計算量

  • 想定できる一般的なシナリオで実行される場合のアルゴリズムのパフォーマンス

領域計算量

  • アルゴリズムが必要とするメモリー領域の総量

静的計算量

  • プログラムが必要とする固定的なメモリーの量

データ構造領域

  • プログラムがデータを保存するために必要なメモリーの量

一時領域

  • アルゴリズムが中間処理のために必要とするメモリーの量。例えば、アルゴリズムがデータを転送するために一時的にコピーするのに必要な領域