Эта статья является продолжением моей предыдущей темы, посвященной динамическому программированию. Я призываю вас сначала прочитать это, чтобы получить полный контекст того, что мы обсуждаем сегодня!
Во-первых, я не могу обещать, что эти знания заставят вас увидеть мир вертикальными линиями зеленого кода; однако в этой статье мы рассмотрим нотацию BigO более подробно, а затем используем ее, чтобы найти наиболее эффективный способ нахождения n-го числа последовательности Фибоначчи с использованием матричного возведения в степень. Матричное возведение в степень — это мощная техника в математике и информатике для быстрого вычисления больших степеней квадратной матрицы. Он имеет множество приложений в различных областях, таких как физика, экономика, криптография и машинное обучение. В этой статье мы рассмотрим использование матричного возведения в степень и продемонстрируем, как его можно использовать для вычисления n-го числа Фибоначчи с временной сложностью O(logn), что является значительным улучшением по сравнению с наивным рекурсивным подходом, который мы видели. в последней статье, которая имеет временную сложность O(2^n) и даже более эффективна по сравнению с подходом динамического программирования, который имеет временную и пространственную сложность O(n).
Учебник по BigO
Я кратко представил нотацию BigO в моей предыдущей статье, но я хочу еще раз вернуться к ней здесь. Нотация BigO — это способ объективно описать временную или пространственную сложность алгоритма. Другими словами, это мера того, сколько времени и ресурсов требуется для решения проблемы определенного размера.
Буква «О» означает «порядок» и используется для описания верхней границы или наихудшего сценария временной сложности алгоритма. Число в скобках описывает, как время работы алгоритма увеличивается по мере увеличения размера входных данных.
Если бы у нас была программа или алгоритм, который всегда выполнял 10 шагов для вывода результата независимо от ввода, мы бы сказали, что у него постоянное время, и мы бы сказали, что BigO равен O(10). Если бы алгоритм всегда выполнял 100 шагов, независимо от входных данных, мы бы точно так же дали этому BigO значение O (100).
В нотации BigO мы исключаем константы и члены более низкого порядка из времени выполнения алгоритма, поскольку они становятся менее значимыми при больших размерах входных данных. Это означает, что O(10) и O(100) считаются имеющими обозначение BigO O(1), потому что они имеют постоянное время выполнения, независимо от размера входных данных. Это правило обобщения непротиворечиво для нотации BigO.
Например, рассмотрим алгоритм, который просто выводит первый элемент массива. Время работы этого алгоритма постоянно или O(1), поскольку оно не зависит от размера массива. Даже если в массиве миллион элементов, алгоритму потребуется столько же времени, чтобы найти первый элемент.
Далее идет линейное время. Допустим, у нас есть алгоритм, который выполняет простую операцию над каждым элементом в списке размером n. Время работы этого алгоритма будет пропорционально количеству элементов в списке или O(n).
Рассмотрим следующий пример:
const arrayOfPets = ["Dog", "Cat", "Fish", "Rock"] const hasPet = (pet: string): boolean => arrayOfPets.includes(pet)
В этом примере метод includes в массиве считается алгоритмом со временем выполнения O(n), так как ему потенциально потребуется найти n элементов в массиве, чтобы определить, данный вход pet содержится в массиве. Теперь вам может повезти, если на входе окажется «Собака», тогда потребуется всего один шаг, однако BigO обеспокоен наихудшим сценарием. Кроме того, для лучшего случая существует обозначение Big Omega, и этот метод имеет время работы Ω(1).
Наконец, алгоритм с нотацией BigO O(log n) считается очень быстрым, поскольку он логарифмически масштабируется с размером входных данных, в то время как алгоритм с нотацией BigO O(2^n ) считается медленным для больших входных данных, поскольку это экспоненциально увеличивает количество шагов по мере роста входных данных. Существуют и другие обозначения, однако они выходят за рамки данной статьи.
Оптимизация нашей функции Фибоначчи
Давайте вспомним наши две реализации, чтобы получить n-е число последовательности Фибоначчи и показать их обозначения BigO:
// O(2^n) - Exponentially increases its running time as `num` increases
const fib = (num: number): number => {
if (num === 0 || num === 1) return 1
const res = fib(num - 1) + fib(num - 2)
return res
}
// O(n) - Linearly increases its running time as `num` increases
const fibMemo = (num: number, memo: Record<number, number> = {}): number => {
if (num === 0 || num === 1) return 1
if (memo[num]) {
return memo[num]
}
const res = fibMemo(num - 1, memo) + fibMemo(num - 2, memo)
memo[num] = res
return res
}
Оказывается, мы можем достичь этого результата с помощью алгоритма O (log n), используя возведение матрицы в степень. Я провел тест, и мы можем ясно видеть, что график согласуется с теорией и четко отображает экспоненциальные, линейные и логарифмические кривые. По мере того, как мы увеличиваем ввод, он в конечном итоге достигает постоянной сложности ~ 20 шагов, независимо от того, насколько еще мы увеличиваем число num .
В конце концов я дошел до ввода 1000, но поскольку для запуска базового алгоритма потребовались бы буквально миллиарды лет, я запустил его только на запомненной и матричной версиях, и вот результаты этого запуска. Результат для заинтересованных был 7.0330367711422765e+208, так что это, мягко говоря, довольно большое число.
Давайте посмотрим на код для этой реализации O(log n):
const fibLog = (n: number): number => {
if (n <= 1) return n;
const matrix = [
[1, 1],
[1, 0],
];
const result = matrixPower(matrix, n - 1);
return result[0][0];
};
const matrixPower = (matrix: number[][], power: number): number[][] => {
if (power === 1) return matrix;
if (power % 2 === 0) {
const half = matrixPower(matrix, power / 2);
return multiplyMatrices(half, half);
}
const half = matrixPower(matrix, Math.floor(power / 2));
const full = multiplyMatrices(half, half);
return multiplyMatrices(full, matrix);
};
const multiplyMatrices = (
matrixA: number[][],
matrixB: number[][]
): number[][] => {
const rows = matrixA.length;
const cols = matrixA[0].length;
const result = [
[0, 0],
[0, 0]
];
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
for (let i = 0; i < cols; i++) {
result[row][col] += matrixA[row][i] * matrixB[i][col];
}
}
}
return result;
};
Как мы сразу видим, реализация намного сложнее, и нам намного труднее визуализировать и рассуждать о ней в нашей ментальной модели. Также есть тройной вложенный цикл for, так как же он эффективен!? Давайте разберем это.
Разбираемся в матрице
Идея состоит в том, чтобы представить последовательность Фибоначчи с помощью матрицы, а затем использовать возведение матрицы в степень для вычисления n-го числа Фибоначчи. Матрица — это многомерный массив, то есть массив массивов. В этом случае внешний массив содержит 2 внутренних массива, каждый из которых имеет длину 2 элемента, например:
const matrix = [ [1, 1], [1, 0], ];
Несколько антиклиматический, я знаю. Я надеялся получить хоть какие-то новые знания о кунг-фу, но, увы, это всего лишь массив. Если посмотреть на эту матрицу как на сетку, мы увидим, что она имеет 2 строки и 2 столбца. Эта конкретная матрица представляет собой коэффициенты повторения Фибоначчи, или, другими словами, описывает, как вычислить следующее число в последовательности на основе двух предыдущих чисел. Первая «строка» соответствует f(n+1) и f(n), а вторая строка соответствует f(n) и f(n-1).
В этой реализации мы используем функцию matrixPower для вычисления степени n-1 матрицы Фибоначчи и функцию multiplyMatrices для умножения двух матриц. Обе эти функции имеют временную сложностьO(log n). Благодаря правилу обобщения общая временная сложность функции fib теперь также составляет O(log n). .
При более внимательном рассмотрении функции matrixPower она принимает два входа, matrix и power, и возвращает матрицу, возведенную в эту степень. Он работает рекурсивно, сначала проверяя, равна ли мощность 1, что является нашим базовым случаем. Если это так, то он просто возвращает матрицу. Если мощность четная, он рекурсивно вычисляет половину мощности и умножает ее саму на себя. Если мощность нечетная, он рекурсивно вычисляет половину мощности минус единицу, умножает ее саму на себя, а затем умножает на исходную матрицу. Результирующая матрица принимает вид:
const result = [ [n, n-1], [n-1, n-2] ]
Поэтому мы можем извлечь n-е число Фибоначчи, взяв result[0][0] (или result[1][0] + result [1][1])
Погружаясь глубже в multiplyMatrix, эта функция принимает две матрицы и возвращает их произведение. Он работает, перебирая каждую строку первой матрицы и каждый столбец второй матрицы, умножая соответствующие элементы и суммируя результаты, чтобы получить элемент в результирующей матрице. row и col представляют строку и столбец результирующей матрицы, а i представляет общее измерение двух матриц. При использовании матричного возведения в степень функция multiplyMatrix вызывается log(n) раз, где n — входное число Фибоначчи.
Последние мысли
Мы более подробно изучили концепцию нотации BigO, которая помогает нам объективно описать временную или пространственную сложность алгоритма. Мы увидели, как возведение матрицы в степень может быть мощным методом для эффективного вычисления больших степеней квадратной матрицы, и, в частности, мы продемонстрировали, как его можно использовать для вычисления n-го числа Фибоначчи за O(log n) временная сложность, которая является значительным улучшением по сравнению с наивно-рекурсивным подходом и даже более эффективна, чем подход динамического программирования, который мы обсуждали ранее.
Оптимизировав нашу функцию Фибоначчи с матричным возведением в степень, мы можем вычислить n-е число Фибоначчи всего за несколько шагов, независимо от того, насколько велико n. Этот подход можно использовать в качестве шаблона для разработки и оптимизации алгоритмов в других областях. Благодаря знаниям, полученным в этой статье, вы теперь можете исследовать и применять матричное возведение в степень для решения проблем, которые могут встретиться на вашем пути.
