Я начал программировать в 7 классе (да, поздно), и тогда это заключалось в решении задачек олимпиадного типа.
Там мне, как полагается, встретилась задача про числа Фибоначчи (вдруг кто забыл,
F_{i+2} = F_{i+1} + F_i ). Условие простое - найдите N-ное число Фибоначчи за константную память и линейное время.К счастью, больших проблем это у меня не вызвало - простой цикл из 3 переменных. У задачи был пункт со звёздочкой - сделайте алгоритм, который работает быстрее, чем за линию. Упёршись в непроходимый для меня тупик, я подсмотрел в решение и увидел то, что в мой мозг поместится не смогло. Но всё же поверил - N-ное число Фибоначчи можно найти за логарифм от N.
Уже в универе, прикола ради я прочитал про логарифмический алгоритм и тогда моих мозгов уже хватило, чтоб понять.
Итак, выражение "
F_{i+2} = F_{i+1} + F_i" можно сформулировать в виде операции умножения матрицы на вектор. Введём матрицу 2x2: [[1, 1], [1, 0]] и вектор 2x1: [F_{i+1}, F_i]. Их умножение даст [F_{i+2}, F_{i+1}], то есть проделает 1 итерацию по ряду Фибоначчи.Получается, что получить
F_n можно, возведя эту матрицу в степень n. Вот тут-то мы и приходим к крутой оптимизации - возведение в n-ную степень можно делать не через n умножений, а через log n! Идея в том, что мы раскладываем результат на множители, у которых показатели степени это степени двойки. То есть
n^29 = n * n^4 * n^8 * n^16. Всего таких множителей будет log n, и получить их все тоже можно за log n. По сути, это эквивалентно переводу n в двоичную систему счисления.Звучит нереально круто. Так я и жил все эти годы, будучи уверенным в том, что знаю ответ на основной вопрос жизни, Вселенной и всего остального - о том, как быстро можно посчитать N-ное число Фибоначчи.
А потом я наткнулся на это видео - "1 секунда на вычисление самого большого числа Фибоначчи". Уже будучи готовым ублажить свой мозг изучением той информации, которую знаю и так, в результате я упал лицом не просто в грязь, а в натуральное говно.
Длина!
Ряд Фибоначчи растёт примерно со скоростью
1.6^n, а значит, количество цифр в записи n- ного числа Фибоначчи растёт линейно относительно n. Как минимум, для записи результата нам нужно линейное время и линейная память. Но это полбеды.Для возведения матрицы степени
n в квадрат нам нужно умножить 2 числа, длина которых около n. А помните сложность возведения чисел в столбик? Аж целый n^2. Таким образом, для очень больших n итоговое количество сделанных операций выглядит как:k * n^2 + k * (n/2)^2 + k * (n/4)^2 + ... = O(n^2) Да, оказалось, что всю жизнь я думал, что алгоритм, работающий за квадрат, работает за логарифм. Это самая большая ошибка в данной области, которую я совершал в жизни.
Однако, как оказалось, существуют способы умножать числа быстрее, чем за квадрат. Начав ресёрчить более подробно, оказалось, что, конечно же, есть специальные математики, занимающиеся алгоритмами в данной области.
А они там такое безумие наоткрывали, что это достойно отдельного поста.
Upd. Тем, кто говорит, что N-ное число Фибоначчи можно посчитать за O(1) аналитической формулой, советую подписаться на канал Stupidity Accumulator
@knowledge_accumulator