計算量を落とすテクニック

概要

特定の区間上の複数回の操作における計算量を落とすテクニックについて考えます。累積和に近い考え方です。

問題設定

という9つの要素を含む数列 がある。数列の添字は から始まるものとする。
ここでは の次の要素は に戻るような循環する数列を考える。
それぞれの要素 に対して、 の最小の要素が何か求める。
ここでは要素 に対して、 回操作したときの最小の要素を ということとする。

例えば、要素 で の場合は、 のうちの最小の要素は であるから
答え である。(要素 は元の数列上で )

ナイーブな方法

各要素 ごとに、それぞれ 回ループして を求める。この場合の計算量は 程度である。

import java.util.Arrays;


public class Sample {

    static int INF = 1 << 30;
    public static void main(String[] args) {

        int[] a = {9, 1, 3, 8, 4, 2, 7, 6, 5};
        int n = a.length;
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(f[i], INF);
        }

        for (int i = 0; i < n; i++) {
            int min = a[i];
            for (int k = 0; k < n; k++) {
                for (int j = 0; j < k; j++) {
                    min = Math.min(min, a[(i-j+n-1)%n]);
                }
                f[i][k] = min;
            }
        }

    }

}

効率的な方法

を から計算した場合、 回目 の操作のときはすでに 回のときまでの最小値は求められている。
例えば、先の例の場合、要素 で の場合は、 のうちで最小の要素を求めるときは
要素 で の場合 の最小値は求められている。 である。
このとき、 の場合の最小の要素は で求められる。
この場合の計算量は である。

import java.util.Arrays;


public class Sample {

    static int INF = 1 << 30;
    public static void main(String[] args) {

        int[] a = {9, 1, 3, 8, 4, 2, 7, 6, 5};
        int n = a.length;
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(f[i], INF);
        }

        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                if (k == 0) {
                    f[i][k] = a[i];
                } else {
                    f[i][k] = Math.min(f[i][k-1], a[(i-k+n)%n]);
                }
            }
        }

    }

}