Help us understand the problem. What is going on with this article?

計算量について考える

計算量について考える

O(n²) -> O(n)へのアルゴリズムを考える。

株価について考える。
安い時に買い、高く売ると大きな利益が出る。
最も大きな利益が出る時を考える。

例えば
入力値: 5 3 1 3 4 3 の場合
最も安い株価が1のときに買い、4のときに売ると利益が最大になる。

また株価を買う -> 株価を売る
の順番であるので上記の例で株価1で買って5で売る。
みたいなことはできない。
時系列的に株価を買うのは株価を売る前でなくてはならない。

実装: O(n²)での計算

n は入力として幾つの数値が渡されるかの値

二重ループを回す。
i > jとすることで、株を買う -> 株を売るという順番を表す。

あとは最大値をmax_profitとして計算をする。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int R[n];
    for(int i = 0; i < n; i++) cin >> R[i];

    int max_profit = R[1] - R[0];
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) {
            max_profit = max(max_profit, R[i] - R[j]);
        }
    }
    cout << max_profit << endl;
}

この場合は計算量がO(n²)となっている。
つまり最初に入力する値の2乗に計算量が比例する。
n=100なら計算量は 10000倍
n= 10000なら 100000000倍

といった具合だ。
つまりnの値によってかなりの速度で計算量は増加していくので、
あまりいい計算方法だとは言えない。

実装: O(n)での計算

2重ループを避け1回のforループで実装を試みる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int R[n];
    for(int i = 0; i < n; i++) cin >> R[i];

    int max_profit = R[1] - R[0];
    int min_n = R[0];
    for(int i = 1; i < n; i++) {
        max_profit = max(max_profit, R[i] - min_n);
        min_n = min(min_n, R[i]);
    }
    cout << max_profit << endl;
}

こんな感じになる。
最初との違いは最小値を変数として保存しておき、
あとはforループを回して最大値を計算する。

この場合は計算量がO(n)なので
n=100なら計算量は 100倍
n= 10000なら 10000倍
つまりnに比例する。

始めの例に比べてnに対する計算量が減ったことがわかる。

n が小さいときは問題ないが、nが大きくなるにつれて
O(n²)とO(n)の計算量はかなりの差が出てくるので、
計算量を意識した実装をしていきましょう。というお話でした。

akilax
営業社員からエンジニアになりました。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away