領域計算量

領域計算量は、アルゴリズムが使うメモリの量を、入力の大きさnに対して表したものです。

■ 試験で押さえるポイント

• O(1)、O(n)のように、オーダー記法で表します。

• 実行時間を表す時間計算量と対になる考え方です。

■ 過去問での着眼点

時間とメモリは、どちらかを減らすともう一方が増えることがあります。

例: 配列をそのまま並べ替えるソートは、追加のメモリがO(1)で済みます。