アルゴリズムとAPG4bについてざっくりまとめてみた(part 2)

目次

メモリとは

メモリとは、コンピュータの記憶領域です。

• メモリは有限である
• 変数を使用した分だけメモリを消費する
• 文字列や配列の変数は、内部の要素数に応じてメモリを消費する

計算量とは

計算量とは、結果を出力するために必要な計算時間や必要な記憶容量の量が、入力に対してどれくらい変化するかを示す指標です。

計算量には時間計算量と空間計算量があります。単に計算量と言われたら、時間計算量を指します。

計算量の表記にはオーダー記法を用います。

時間計算量とは

時間計算量とは、「プログラムの実行に必要な計算ステップ数が入力に対してどのように変化するか」を表す指標です。

ステップ数とは

ステップ数とは、あるアルゴリズムが問題を解くにあたって実行しなければならない処理や操作などの回数のことです。(四則演算、数値の比較、入出力処理等)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> A(N);
 
  // O(N)
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
 
  // O(N log N)
  sort(A.begin(), A.end());
 
  // O(N)
  for (int i = 0; i < N; i++) {
    cout << A.at(i) << endl;
  }
}

空間計算量

空間計算量とは、「プログラムの実行に必要なメモリの量が入力に対してどのように変化するか」を表す指標です。

オーダー記法とは

オーダー記法とは、関数の極限における値の変化を大まかに評価するための記法です。アルゴリズムの計算量の評価に用いられます。計算量を厳密に評価しているわけではなく、大まかに評価するための記法です。

正確に比較する必要がある場合は、実際に時間を計測して比較する必要があります。

オーダー記法の書き方

ステップ1：各項にある係数を省略する。ただし定数については1とする。 ステップ2：Nを大きくしたときに一番影響が大きい項を取り出し、O(項)と書く。

注) 「一番影響が大きい項」というのは、Nを大きくしていったときに「大きくなるスピードが最も速い項」のことです。

ログ

log xNという式は「xを何乗したらNになるか」を表します。 log 2 8という式は、「長さ8の棒を長さが1になるまで半分に切る回数」を表します。

オーダー記法ではlogの底は省略されます。省略された場合、底は2を表します。

このように計算量に出てくるlogは「半分にする回数」を表すことが多いです。 logNはNに対して非常に小さくなるので、計算量の中にO(logN)が出てきた場合でも実行時間にそこまで影響しないことが多いです。

入力に適した計算量のアルゴリズムを選択する

1秒くらいで計算が終わるようなプログラムを作ろうというときは、 入力の大きさの上限を見積もった上で1秒以内に収まるような計算量のアルゴリズムを選択する必要があります。

プログラムの実行を1秒以内に収めたい場合

1. 入力の大きさを見積もる
2. その入力で1秒以内に計算できるような計算量のアルゴリズムを選択する。

複数の入力がある場合のオーダー記法

2つの入力NとMを受け取る場合はO(N+M),O(NM),O((N+M)logN)のように書きます。

STLの関数の計算量

STLの関数	計算量(配列の要素数N)
sort	O(NlogN)
reverse	O(N)

参考記事

時間計算量とは - 意味をわかりやすく - IT用語辞典 e-Words