計算量とオーダー ​

1. ランダウの記号 ​

実行時間では再帰関数の実行速度を大まかに見積もったが、ランダウの記号という考え方を使うことでより良く概算することができる。ランダウの記号は以下のように定義される。

であるとき、と書き、「 は のオーダーである」という。

例えば、 のオーダーは となる。

2. 計算量 ​

問題の大きさ に対して、それを解くために必要なリソースの量を関数として得ることができ、これをランダウの記号で表すと何かと都合が良い。ここでは特に実行時間について着目する。

例えば、std::vector<int>の最大の要素を得る関数のオーダーは、要素の数 に対して となる。

int max_element(std::vector<int> v) {
    int current_max = INT_MIN;
    // ここでn回ループを回している
    for (int i = 0; i < v.size(); i++) {
        current_max = max(current_max, v[i]);
    }
    return current_max;
}