概要
パソコンが使えるメモリには限界があります。多くのパソコンで快適に動くプログラムを書くには空間計算量(Time Complexity)を意識する必要があります。
空間計算量とは、ある問題を解くためにパソコンが必要とするメモリのことです。通常はビッグオー記法を使ってO(1)、O(n)などと表します。
空間計算量は小さいほど良いです。つまり空間計算量がO(1)のアルゴリズムはO(n)のアルゴリズムよりも優れている評価できます。しかしアルゴリズムを測る尺度として他にも時間計算量などがあり、空間計算量だけでアルゴリズムの全てを評価できるわけではありません。
ビッグオー記法の簡単な説明
空間計算量においてビッグオー記法とは、入力が使うメモリの大きさnに対して、パソコンが処理に必要とするメモリをざっくりと示すものです。パソコンが必要とするメモリが定数ならO(1)、入力に必要なメモリに比例する程度ならO(n)などと書きます。
空間計算量の種類
空間計算量には二種類あります。
- Auxiliary Space Complexity
- Total Space Complexity
Auxiliary Space Complexityとは、処理のために追加で必要になったメモリの空間計算量です。一方でTotal Space Complexityは「Auxiliary Space Complexity」と「入力に必要なメモリ」とを両方考慮したものです。
以下のバブルソートの例ではAuxiliary Space ComplexityはO(1)であり、Total Space ComplexityはO(n)です。
特に注意書きがない場合、Space ComplexityはAuxiliary Space Complexityの方を指している場合が多いです。
バブルソートの空間計算量
バブルソートとは
リスト内の数字を小さい順にならべるソートアルゴリズムの１つです。リストの最初の要素から始まり、隣り合った２つの要素を順に比較していき、もし小さい順に並んでいなかったらその２つの要素を入れ替えるということを繰り返します。
https://en.wikipedia.org/wiki/Bubble_sort#/media/File:Bubble-sort-example-300px.gif
バブルソートの空間計算量
バブルソートのAuxiliary Space ComplexityはO(1)です。処理を実行するために追加で必要になるメモリは定数だからです。バブルソートでは２つ要素の比較、交換だけできればいいので、比較用の変数left, rightや、交換のために一時的に使う変数tempを使うだけでこと足ります。
一方で入力に必要なメモリはnです。Auxiliary Space ComplexityのO(1)と、入力に必要なメモリO(n)の両方を考慮し、Total Space ComplexityはO(n)と決まります。
他のアルゴリズムの空間計算量を調べるには？
Wikipediaにアルゴリズムの空間計算量(Space Complexity)が記載されています。
例としてバブルソートについて書かれたWikipediaの記事をご覧ください。