производительность — ряд Фибоначчи n-го числа в php с O (log N)

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

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

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

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

Простая реализация в 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];
}

Но, как вы, вероятно, видите, мы все еще не избавились от цикла for, то есть у нас все еще есть временная сложность 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) космическая сложность.

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

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