Серия фибоначчи n-е число в php с O (log N)

Question

Ищет решение, в котором код сложности O(log N). space complexity будет O(1)

Я попытался следующие

function fib($a, $b, $N) { 

    $c = ""; 
    if ($N == 0) { 
     return intval($a); 
    } else if ($N == 1) { 
     return intval($b); 
    } else { 
     for ($i = 1; $i <= $N - 1; $a = $b, $b = $c, $i++) { 
      $c = ($a) + ($b); 
     } 
    } 
    return intval($c); 
} 

исходной задачей

Answer 1

Так относительно вашего кода, вы достигли пространства сложности O(1), но ваше время сложности еще O(n), так как он все равно примет n исполнения цикла for, чтобы найти номер n'th.

Во-вторых, функция, которую вы пытаетесь создать, может генерировать последовательность фибоначчи, но также может генерировать другие последовательности, используя тот же принцип, но начиная с разных чисел.

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

Мы можем создать матрицу слева от двух начальных чисел. Затем мы можем поднять его до уровня n-1, и мы получим желаемое число в верхнем левом углу матрицы результатов.

Простая реализация в PHP может выглядеть следующим образом:

/** 
* Takes two 2x2 matrices as parameters, multiplies them and returns the result. 
*/ 
function multiply_matrix(array $a, array $b) { 
    return [ 
     [ 
      $a[0][0]*$b[0][0] + $a[0][1]*$b[1][0], 
      $a[0][0]*$b[0][1] + $a[0][1]*$b[1][1] 
     ], 
     [ 
      $a[1][0]*$b[0][0] + $a[1][1]*$b[1][0], 
      $a[1][0]*$b[0][1] + $a[1][1]*$b[1][1] 
     ] 
    ]; 
} 

/** 
* Multiplies a 2x2 matrix to the n'th power 
*/ 
function power_of_matrix(array $matr, $n) { 
    $result = $matr; 

    for ($i = 1; $i < $n; ++$i) { 
     $result = multiply_matrix($result, $matr); 
    } 

    return $result; 
} 

function gf($a, $b, $n) { 
    if ($n == 0) { 
     return $a; 
    } 

    $result = power_of_matrix([[$a+$b, $b], [$b, $a]], $n - 1); 

    return $result[0][0]; 
} 

Но, как вы, вероятно, можете видеть, мы до сих пор не избавились от для цикла, то есть у нас еще есть время сложность O(n). Чтобы, наконец, получить ниже линейного времени, нам нужно оптимизировать power_of_matrix().

Прямо сейчас мы умножаем матрицы n раз. Но действительно ли мы должны это делать? Давайте разберем простое уравнение:

2^8 = 256 = 2^4 * 2^4 = 2^4 * 2^2 * 2^2 = 2^4 * 2^2 * 2 * 2 

Рассчитав n/2 «й степени, мы можем сохранить результат и умножить на него, экономя нам много шагов умножения. Нам просто нужно убедиться, что, если мощность еще не четная, мы умножаем результат на дополнительное время.

же логика применима и к матрицам, и мы можем использовать его для оптимизации power_of_matrix так:

function power_of_matrix(array $matr, $n) { 
    if ($n == 0 || $n == 1) { 
     return $matr; 
    } 

    $result = power_of_matrix($matr, intval($n/2)); 
    $result = multiply_matrix($result, $result); 

    if ($n % 2 != 0) { 
     return multiply_matrix($result, $matr); 
    } 

    return $result; 
} 

Теперь решение имеет временную сложность O(log n). Однако, поскольку мы используем рекурсию здесь, и из-за природы массивов PHP, этот метод не имеет сложности O(1).

Для этого нам нужно передать матрицу по ссылке и изменить ее, а не возвращать новую матрицу результатов каждый раз.

Надеюсь, это поможет вам в понимании и решении проблемы.