Комментарии 28
А зачем матрица T? Тут же вроде всегда было вектора достаточно…
А какие вы знаете удивительные алгоритмы? — Знаем бессмысленный и беспощадный нормальный алгоритм Маркова для деления чисел habr.com/ru/post/110004
Однажды у меня было удивление при чтении математического справочника 1950-1960-х годов. Там было много хаков, позволяющих просто посчитать вещи, которые я без компьютера не посчитаю.
Алгоритм сортировки массива за линию Radix sort сильно ломает шаблоны
Ну, он довольно условно за линию: он сортирует за O(N*число_разрядов). Если предположить, что все числа разные – то нам надо по крайней мере log(N) разрядов для их представления, и получаем всё тот же O(N*log(N)).
Мы же можем сортировать не поразрядно а побайтого, тоесть int64 будем сортировать по 8 байтам, в этом случае получим O(N). Другое дело, что на практике там слишком большой постоянный множитель + нужна доп память, сортировки сравнением оказываются быстрее по итогу.
Получите N*log256(N), то же самое :-)
На самом деле это один из примеров, показывающий, что асимптотики порой недостаточно для оценки. Допустим, у нас не больше миллиона чисел – тогда log256(N)<=2.5, log2(N)<=20. Т.е. логарифм можно смело заменять на (не такой уж большой) постоянный множитель.
Ещё прикольнее алгоритмы, в сложности которых фигурирует обратная функция Аккермана, например, ru.wikipedia.org/wiki/Алгоритм_Краскала – она вроде и растёт от N, но настолько медленно, что проще забить.
На самом деле это один из примеров, показывающий, что асимптотики порой недостаточно для оценки. Допустим, у нас не больше миллиона чисел – тогда log256(N)<=2.5, log2(N)<=20. Т.е. логарифм можно смело заменять на (не такой уж большой) постоянный множитель.
Ещё прикольнее алгоритмы, в сложности которых фигурирует обратная функция Аккермана, например, ru.wikipedia.org/wiki/Алгоритм_Краскала – она вроде и растёт от N, но настолько медленно, что проще забить.
Так-то и матрицы можно быстрее чем за куб перемножать.
НЛО прилетело и опубликовало эту надпись здесь
Это хорошие алгоритмы, но это же не динамическое программирование.
С (целочисленными) последовательностями и Фибоначчи в частности есть засада, они быстро выходят за размер целого числа. Сотое число Фибоначчи уже не влезает в 64 бита. Так что если считать сложность алгоритма честно, то нужно учитывать что умножение чисел выполняется не за константу, а становится дороже при росте чисел :). Получится уже не логарифм.
Мой любимый пример — алгоритм Шонхаге-Штрассена (?) для умножения больших чисел через преобразование Фурье за O(NlogN). Составляете последовательность из цифр числа A, применяете FFT, то же для числа B, потом их (FFT) перемножаете попарно, применяете обратное преобразование (IFFT), результат – цифры произведения А и B.
Пожалуй, самое сильное "ВАУ" за всю мою программистскую карьеру.
Деталей не помню, выглядит как-то так:
import numpy as np
A = [0, 0, 0, 0, 0, 0, 0, 2] # 2
B = [0, 0, 0, 0, 0, 1, 3, 2] # 132
FC = np.fft.fft(A) * np.fft.fft(B)
C = np.fft.ifft(FC) # <-- Тут должна быть какая-то возня с С, типа переносов между разрядами
print(" ".join([str(round(abs(c))) for c in C])) # Prints "0 0 0 0 2 6 4 0"
Возможно стоило упомянуть о том, что некоторые рекуррентные последовательности можно вычислить за O(1). Например, произвольный член ряда вариации Фибоначчи, который начинается не с {1,1,2,...}, а с {a,b,a+b,...} можно вычислить через функцию
(Power((1+Sqrt(5))/2, n)*((-5+3*Sqrt(5))*a - (-5+Sqrt(5))*b) - Power(2/(1+Sqrt(5)), n)*((5+3*Sqrt(5))*a - (5+Sqrt(5))*b)*Cos(n*Pi))/10Видимо вы имеете в виду Формулу Бине, которая также опирается на возведение в степень, и если эту операцию мы считаем O(1), то и представленный алгоритм тоже O(1), но вообще это некорректно.
Нет — в данном случае формула Бине является лишь частным случаем при a=1 и b=1, и, к слову, выводится она не через возведение в степень, а через производящие функции.
Выводится через производящие функции, но для подсчета конкретного числа Фибоначчи с её помощью нужно вычислять два возведения в степень
А возведение в степень — через умножение логарифмов. А логарифм можно посчитать даже на линейке.
Сотрите, у меня было два основных тезиса
1) Вычисление степени матрицы можно свести к формулам наподобие того, что вы выписали
умножая матрицу в степени на вектор (1, 1) получается последовательность Фибоначчи, умножая на (a, b) получается вариация, о которой Вы писали.
2) Некорректно считать, что такое возведение в степень — это O(1). Чтобы вычислить a^n по формуле exp(log(a) * n) нужно обеспечить достаточную точность при работе с вещественными числами, эта точность зависит от размера результата, точнее сказать не могу — не разбирался.
1) Вычисление степени матрицы можно свести к формулам наподобие того, что вы выписали
Диагонализация матрицы из статьи
умножая матрицу в степени на вектор (1, 1) получается последовательность Фибоначчи, умножая на (a, b) получается вариация, о которой Вы писали.
2) Некорректно считать, что такое возведение в степень — это O(1). Чтобы вычислить a^n по формуле exp(log(a) * n) нужно обеспечить достаточную точность при работе с вещественными числами, эта точность зависит от размера результата, точнее сказать не могу — не разбирался.
1) давайте пойдём дальше — как свести вычисления с матрицами к дробному отрицательному n или решить прямо противоположную задачу — зная значение члена ряда Фибоначчи найти его порядковый номер.
2) O(1) значит независимость от n, а не сложность вычисления отдельно взятой операции для вычисления конечного результата. К тому же, в вещественных числах вычисление логарифма не зависит (сильно, какие-то колебания конечно же есть) от аргумента, это совершенно точно (а я разбирался и даже писал свою реализацию).
2) O(1) значит независимость от n, а не сложность вычисления отдельно взятой операции для вычисления конечного результата. К тому же, в вещественных числах вычисление логарифма не зависит (сильно, какие-то колебания конечно же есть) от аргумента, это совершенно точно (а я разбирался и даже писал свою реализацию).
К тому же, в вещественных числах вычисление логарифма не зависит от аргумента
Если Вы говорите об операциях скажем в 64-битном double или любом другом конечном типе хоть с плавающей, хоть с фиксированной точкой, то я согласен — вычисление логарифма не зависит от аргумента. Проблема в том, что в этих вычислениях будет погрешность, которая ограничена снизу в силу конечности представления. И этой точности не будет достаточно для вычисления произвольного числа Фибоначчи, так как последовательность Фибоначчи не ограничена, а следовательно не ограничено и количество значащих цифр в представлении чисел Фибоначчи.
«За линию» очень режет слух, почему нельзя было немного уточнить: «с линейной сложностью»?
Заголовок спойлера
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Удивительно быстрые алгоритмы