[Математика] Вычисляем последовательность Фибоначчи за логарифмическое время (перевод)
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
В преддверии старта базового кура "Математика для Data Science" приглашаем вас записаться на бесплатный демо-урок, который проведут наши эксперты.А прямо сейчас предлагаем перевод полезной статьи.
Наивное вычисление знаменитой последовательности Фибоначчи производится за экспоненциальное время. Большинство людей могут сообразить, как сделать это за константное время. Но под силу ли нам улучшить этот показатель? Даже не сомневайтесь.Что такое последовательность Фибоначчи?Это классический бесконечный числовой ряд, в котором n-й член представляет собой сумму двух предыдущих членов. Первые два члена - 1 и 1. Третий - 2, четвертый - 3, затем следует 5, 8 и т. д.
Как это вычисляется обычно?Чаще всего люди склонны использовать наивное рекурсивное решение, которое вызывает функцию на двух предыдущих членах. Очевидно, что это решение невероятно неэффективно, потому что выполняется за экспоненциальное время (каждый вызов функции разветвляется на два отдельных вызова для вычисления n-1 и n-2).
// calculates nth term of fibonacci, 1 indexed
Procedure Fib_Naive(int n):
if(n < 3):
return 1;
end_if
return Fib_Naive(n-1) + Fib_Naive(n-2)
end_Fib_Naive
Улучшенный подходРешением получше была бы реализация рекурсивной функции, которая может либо запоминать, либо сохранять временную переменную, содержащую два предыдущих члена.В качестве альтернативы мы могли бы просто использовать временную переменную (temp) и производить вычисления итеративно, что предпочтительнее, поскольку рекурсия обычно занимает больше времени, чем итерационные решения (потому что вызовы, помещаемые в стек, требуют дополнительных инструкций сборки кода).
// calculates nth term of fibonacci, 1 indexed
Procedure Fib(int n):
if(n < 3): return 1;
int prev = 1;
int cur = 1;
for i = 3...n:
int temp = cur;
cur += prev;
prev = temp;
end_for
return cur;
end_Fib
Новый подходПрежде чем мы начнем, давайте слегка освежим базовые знания из линейной алгебры.Вспомните единичную матрицу, по главной диагонали которой расположены единицы, а все остальные элементы равны нулю:
Произведение любой матрицы и единичной матрицы равно самой матрице, и наоборот, как показано выше.
Если мы поменяем местами две строки единичной матрицы и умножим ее на другую матрицу, это будет эквивалентно перестановке тех же двух строк у другой матрицы:
Такая матрица (в центре) называется матрицей перестановок.Теперь предположим, что мы установили единицу в элемент в нижнем правом углу такой матрицы перестановок и умножили ее на вектор 2x1 (a, b). Что произойдет? По правилам умножения матриц, это поменяет местами первые две строки и сделает самый нижний элемент результирующего вектора равным (a + b).
Теперь мы можем вернуться к нашей задаче. Помните наше итеративное вычисление последовательности Фибоначчи? В этом уравнении a представляет предыдущий ((n-1)-й) элемент, а b представляет текущий.Приведенное выше уравнение умножения матриц делает то же самое.Оказывается, если мы возведем матрицу слева в n-ю степень и умножим ее на вектор (0, 1), мы получим n-й элемент последовательности Фибоначчи.
Откуда же логарифм?Два слова: многократное квадрирование. Вместо того, чтобы умножать левую матрицу n раз, мы можем использовать предыдущие произведения умножения матриц, чтобы получить ответ быстрее.Матрица, возведенная в 8-ю степень, может быть вычислена путем возведения в квадрат исходной матрицы, затем возведения в квадрат для достижения 4-й степени, а затем еще одного возведения в квадрат. Это быстрее, чем 8 раз умножать одну и ту же матрицу.Таким образом, мы получаем следующий прогноз производительности:
В целях уменьшения путаницы, поскольку реализация на конкретном языке программирования может быть сложной, вот фактическая реализация на Java (а не псевдокод, как в предыдущих примерах).Здесь нет матриц, но реализация все-равно использует преимущества многократного квадрирования, как обсуждалось ранее, для достижения искомой логарифмической производительности:
public int fib(int N) {
if(N == 0) return 0;
int[] sol = fibHelp(N);
return sol[1];
}
public int[] fibHelp(int n) {
if(n == 1) {
return new int[] {0,1};
}
int m = n/2;
int[] temp = fibHelp(m);
int fPrev = temp[0];
int fCur = temp[1];
int prev = (fPrev * fPrev) + (fCur * fCur);
int cur = fCur * (2 * fPrev + fCur);
int next = prev + cur;
if(n % 2 == 0) {
return new int[] {prev, cur};
}
else {
return new int[] {cur, next};
}
}
*Примечание: Хотя может возникнуть соблазн сказать, что мы значительно сократили время вычислений и что сложность этой реализации может быть классифицирована как логарифмическая, все же есть один нюанс, который мы должны учитывать: временная сложность самой арифметики.Самый быстрый из известных алгоритмов умножения выполняется за O(n log(n)). Технически количество арифметических операций не соответствует заявленному. Однако глубина нашей рекурсии логарифмическая, как видно из примера кода.
Записаться на открытый вебинар.
===========
Источник:
habr.com
===========
===========
Автор оригинала: Alan Chen
===========Похожие новости:
- [Программирование, Go] Что такое горутины и каков их размер? (перевод)
- [Программирование, Машинное обучение] Машинное обучение с Dask (перевод)
- [Python, Data Engineering] Python API в Delta Lake — простые и надежные операции Upsert и Delete (перевод)
- [Программирование, Разработка под iOS, Swift] Разница между @StateObject, @EnvironmentObject и @ObservedObject в SwiftUI (перевод)
- [Python, Программирование, Машинное обучение] Быстрый градиентный бустинг с CatBoost (перевод)
- [Разработка под iOS, Системы сборки, Облачные сервисы] Интеграция CI/CD для нескольких сред с Jenkins и Fastlane. Часть 2 (перевод)
- [Математика, Бизнес-модели] Цепочки поставок с учетом производственно-коммерческих ограничений
- [Java, DevOps, Kubernetes] Пример развертывания Spring Boot-приложения в Kubernetes (перевод)
- [Cisco, Сетевые технологии] VxLAN фабрика часть 4. Multipod
- [] Жуткие байки айтишников
Теги для поиска: #_matematika (Математика), #_matematika (математика), #_posledovatelnost_fibonachchi (последовательность фибоначчи), #_blog_kompanii_otus._onlajnobrazovanie (
Блог компании OTUS. Онлайн-образование
), #_matematika (
Математика
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 19:22
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
В преддверии старта базового кура "Математика для Data Science" приглашаем вас записаться на бесплатный демо-урок, который проведут наши эксперты.А прямо сейчас предлагаем перевод полезной статьи.
 Наивное вычисление знаменитой последовательности Фибоначчи производится за экспоненциальное время. Большинство людей могут сообразить, как сделать это за константное время. Но под силу ли нам улучшить этот показатель? Даже не сомневайтесь.Что такое последовательность Фибоначчи?Это классический бесконечный числовой ряд, в котором n-й член представляет собой сумму двух предыдущих членов. Первые два члена - 1 и 1. Третий - 2, четвертый - 3, затем следует 5, 8 и т. д.  Как это вычисляется обычно?Чаще всего люди склонны использовать наивное рекурсивное решение, которое вызывает функцию на двух предыдущих членах. Очевидно, что это решение невероятно неэффективно, потому что выполняется за экспоненциальное время (каждый вызов функции разветвляется на два отдельных вызова для вычисления n-1 и n-2). // calculates nth term of fibonacci, 1 indexed
Procedure Fib_Naive(int n): if(n < 3): return 1; end_if return Fib_Naive(n-1) + Fib_Naive(n-2) end_Fib_Naive // calculates nth term of fibonacci, 1 indexed
Procedure Fib(int n): if(n < 3): return 1; int prev = 1; int cur = 1; for i = 3...n: int temp = cur; cur += prev; prev = temp; end_for return cur; end_Fib  Произведение любой матрицы и единичной матрицы равно самой матрице, и наоборот, как показано выше. Если мы поменяем местами две строки единичной матрицы и умножим ее на другую матрицу, это будет эквивалентно перестановке тех же двух строк у другой матрицы:  Такая матрица (в центре) называется матрицей перестановок.Теперь предположим, что мы установили единицу в элемент в нижнем правом углу такой матрицы перестановок и умножили ее на вектор 2x1 (a, b). Что произойдет? По правилам умножения матриц, это поменяет местами первые две строки и сделает самый нижний элемент результирующего вектора равным (a + b).  Теперь мы можем вернуться к нашей задаче. Помните наше итеративное вычисление последовательности Фибоначчи? В этом уравнении a представляет предыдущий ((n-1)-й) элемент, а b представляет текущий.Приведенное выше уравнение умножения матриц делает то же самое.Оказывается, если мы возведем матрицу слева в n-ю степень и умножим ее на вектор (0, 1), мы получим n-й элемент последовательности Фибоначчи.  Откуда же логарифм?Два слова: многократное квадрирование. Вместо того, чтобы умножать левую матрицу n раз, мы можем использовать предыдущие произведения умножения матриц, чтобы получить ответ быстрее.Матрица, возведенная в 8-ю степень, может быть вычислена путем возведения в квадрат исходной матрицы, затем возведения в квадрат для достижения 4-й степени, а затем еще одного возведения в квадрат. Это быстрее, чем 8 раз умножать одну и ту же матрицу.Таким образом, мы получаем следующий прогноз производительности:  В целях уменьшения путаницы, поскольку реализация на конкретном языке программирования может быть сложной, вот фактическая реализация на Java (а не псевдокод, как в предыдущих примерах).Здесь нет матриц, но реализация все-равно использует преимущества многократного квадрирования, как обсуждалось ранее, для достижения искомой логарифмической производительности: public int fib(int N) {
if(N == 0) return 0; int[] sol = fibHelp(N); return sol[1]; } public int[] fibHelp(int n) { if(n == 1) { return new int[] {0,1}; } int m = n/2; int[] temp = fibHelp(m); int fPrev = temp[0]; int fCur = temp[1]; int prev = (fPrev * fPrev) + (fCur * fCur); int cur = fCur * (2 * fPrev + fCur); int next = prev + cur; if(n % 2 == 0) { return new int[] {prev, cur}; } else { return new int[] {cur, next}; } } Записаться на открытый вебинар.
=========== Источник: habr.com =========== =========== Автор оригинала: Alan Chen ===========Похожие новости:
Блог компании OTUS. Онлайн-образование ), #_matematika ( Математика ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 19:22
Часовой пояс: UTC + 5