計算量

読了目安 約3分

O 記法で実行回数を見積もり、制約から解法を選ぶ。TLE を体験する演習付き。

書いたプログラムは 1 秒で終わるのか、それとも 1 時間かかるのか。 実行する前に見積もる道具が計算量です。

O 記法

実行回数のおおまかな増え方を計算量と呼び、O 記法で表します。 「おおまか」の数え方は 2 つだけです。

• 定数倍は無視する: 3N 回でも N 回でも O(N)
• 影響の小さい項は無視する: N² + N 回は O(N²)

N が大きくなると、一番強く増える項だけで速さがほぼ決まるからです。

体感表

N = 100,000 のときの実行回数で、速さの感覚をつかんでください。

O(log N) は、「N を半分にしながら進む」処理で現れます。

1 秒で約 10^8 回

単純な計算なら、1 秒におよそ 10^8 回が目安です。 問題の制約と組み合わせると、コードを書く前に解法を選べます。

思考の型は「制約を見る → 許される計算量を逆算する → その範囲に収まる解法を考える」です。 たとえば N ≤ 100,000 の問題で 2 重ループを書くと 100 億回になり、間に合いません。

実際に測ってみる

ContinuousClock を使うと、処理にかかった時間を測れます。

let clock = ContinuousClock()
for n in [500, 1000, 2000] {
    var count = 0
    let time = clock.measure {
        for _ in 0..<n {
            for _ in 0..<n {
                count += 1
            }
        }
    }
    print("N = \(n): \(count) 回の計算に \(time)")
}

N を 2 倍にするたびに、時間が約 4 倍になっているはずです。 これが O(N²) の増え方です。

試してみよう: 配列を [1000, 2000, 4000] に変えて、4 倍ずつの伸びが続くことを確かめてください。

エディタでの実行は数秒で打ち切られます。 採点で時間切れになると TLE (Time Limit Exceeded) と表示されます。

学びどころ

演習

N 個の整数が入力されます。 値が等しい 2 個の組が何組あるかを出力してください。 入力例の 1 2 1 3 1 では、3 つの 1 から 2 個を選ぶ 3 組が答えです。

1 行目に N、2 行目に N 個の整数が空白区切りで入力されます。

制約: 2 ≤ N ≤ 25,000、値は 1 以上 9 以下

最後のケースは N = 25,000 です。 2 重ループの O(N²) 解は TLE になるので、O(N) の解き方を考えてください。 ヒント: 同じ値がいままでに何個出たかを数えながら足していくと、1 重ループで済みます。

入力例:
5
1 2 1 3 1

出力例:
3

let n = Int(readLine()!)!
let a = readLine()!.split(separator: " ").map { Int($0)! }
var seen = [Int](repeating: 0, count: 10)   // seen[v] = 値 v がこれまでに出た個数
var answer = 0
for i in 0..<n {
    answer += seen[a[i]]   // 同じ値の登場回数の分だけ組が増える
    seen[a[i]] += 1
}
print(answer)