Динамическое программирование против матрицы преобразования в задачах линейной повторяемости

Проблема линейной рекуррентности означает проблему, которую можно представить в виде функции, в которой каждый член является линейной комбинацией предыдущих. Классический пример - это Фибоначи:

Несмотря на то, что эту проблему можно закодировать итеративным способом, я уверен, что вы согласны со мной, когда я говорю, что рекурсивная задача более элегантна:

public long fibonacci(int n) {
    if (n == 1 || n == 2)
        return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Однако эта первая версия не выглядит достаточно эффективной. Он снова и снова пересчитывает множество функций. Например, fibonacci (5) необходимо вычислить fibonacci (4) и fibonacci (3). Обратите внимание, что для fibonacci (4) также требуется fibonacci (3), поэтому он вычисляется снова. Плохо.

Чтобы решить эту проблему, мы можем добавить мемоизацию для хранения вычисленных fibonacci (n):

public long fibonacci(int n, HashMap<Integer, Long> mem) {
    if (n == 1 || n == 2)
        return 1;
    if (mem.containsKey(n))
        return mem.get(n);
    long fib = fibonacci(n - 1, mem) + fibonacci(n - 2, mem);
    mem.put(n, fib);
    return fib;
}

Сделанный! Теперь это выглядит довольно эффективно. Фактически, мы можем подумать, что приведенное выше решение является наиболее эффективным, но это не так. Продолжай читать.

Каждую линейную задачу, основанную на рекуррентности, можно решить с помощью следующей формулы:

Где T - это матрица преобразования, а F - это матрица столбцов, содержащая начальные значения. Но как получить матрицы T и F?

Во-первых, нам нужно получить значение k. k определяется как количество предыдущих значений, необходимых для получения «текущего» (т. е. n). В нашем примере, Фибоначчи, k = 2,, потому что нам нужны f (n-1) и f (n-2), чтобы получить f (n); 2 предыдущих значения.

Мы определяем F как матрицу столбцов, где каждая строка от f (1) до f (k):

В нашем примере k = 2, f (1) = 1 и f (2) = 1, поэтому:

Когда у нас есть F, нам понадобится матрица преобразования T. T - это матрица kxk, где:

  • каждая строка заполняется значением 0, кроме столбца (i + 1) th, который равен 1; , где i - индекс строки.
  • последняя строка состоит из коэффициентов каждого предыдущего члена.

Выражение Фибоначчи можно переписать следующим образом:

Коэффициенты равны 1 и 1, поэтому мы определяем T как:

У нас уже есть все элементы, необходимые для построения нашей формулы:

Вот реализация Java:

public long fibonacci(int n) {
    if (n == 1 || n == 2)
        return 1;
    long[][] t = {{0, 1}, {1, 1}};
    long[][] f = {{1}, {1}};
    long[][] tPow = powMatrix(t, n - 1);
    return multMatrices2x2and2x1(tPow, f)[0][0];
}
private long[][] powMatrix(long[][] matrix, int pow) {
    if (pow == 1)
        return matrix;
    long[][] powM = powMatrix(matrix, (int) Math.floor(pow / 2));
    if (pow % 2 == 0)
        return multMatrices2x2(powM, powM);
    return multMatrices2x2(multMatrices2x2(powM, powM), matrix);
}

private long[][] multMatrices2x2(long[][] m1, long[][] m2) {
    return new long[][]{
            {m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0], m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]},
            {m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0], m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]}
    };
}

private long[][] multMatrices2x2and2x1(long[][] m1, long[][] m2) {
    return new long[][]{
            {m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]},
            {m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]}
    };
}

Контрольные точки

После нескольких тестов с обеими версиями Фибоначчи вот некоторые цифры:

Похоже, версия матрицы преобразования немного быстрее.

Надеюсь, вам понравился пост!