Генерация серии Фибоначчи с использованием матриц

Question

Есть один вопрос, который был опубликован около Fibonacci Series, о котором я знаком с ним. Но есть несколько ответов и связанных с ним вопросов. Поскольку я копался в этом с некоторым интересом, есть решение, которое есть linked to here

Этот алгоритм решает проблему с помощью O (log (n)) весьма впечатляюще. Но я не мог понять логику и так называемую выраженность Матрицы [смотрел wiki, но не мог с ней относиться].

Так любезно, что любой может объяснить, как именно они достигли с более подробной информацией и лучшим объяснением [если вы можете объяснить с помощью кода, предпочитаете на Java, очень полезно].

Спасибо :)

Answer 1

То, что вы должны понять алгоритм, а не реализации.

Первое, что вы должны понять, что этот алгоритм не даст вам все числа Фибоначчи, только те, с п что является степенью 2.

Вторая вещь, что умножение матриц постоянного размера, конечно, принимает постоянное (O (1)) время.

Трюк теперь состоит в том, чтобы правильно отметить, что число n-й фибоначчи может быть сформировано путем умножения матрицы n, указанной в вашей ссылке, которое я назову M.

Теперь вы получаете сложность журнала, «переупорядочивая» операции матрицы, например, M * (M * (M * M)) до (M * M) * (M * M). С каждой квадратичной матрицей вы переходите к M^2n вместо M^n + 1.