Пункт 1
Числа Фибоначчи, вычисление через матрицы
Числа фибоначчи - последовательность чисел, заданная рекурсивно:
F(n)={[1,,n∈{1,2}],[F(n-1)+F(n-2),,n>2])
иногда определяют F(0)=0,F(1)=1, это эквивалентно, но дает F(0)
Вычисление с помощью матриц
Можно составить матричное уравнение:
([0,1],[1,1])⋅([F(n-1)],[F(n)])=([F(n)],[F(n-1)+F(n)])=([F(n)],[F(n+1)])
Тогда, чтобы найти F(n):
([F(n)],[F(n+1)])=([0,1],[1,1])n⋅([F(1)],[F(2)])
([F(n-1)],[F(n)])=([0,1],[1,1])n⋅([F(0)],[F(1)])
По такой формуле можно найти F(n) за O(n*(log_)(n)), если использовать бинарное возведение в степень на матрице
Алгоритм Карацубы
Эта штука позволяет быстро перемножать числа или многочлены: тут будет с многочленами, но если x заменить на основание системы счисления, получится перемножение чисел.
Мы хотим свести задачу умножения двух многочленов размера 2*n к нескольким умножениям многочленов размера n:
Пусть:
a(x)=xn⋅(a_h)(x)+(a_l)(x),
b(x)=xn⋅(b_h)(x)+(b_l)(x).
Посчитаем три многочлена:
Тогда:
a(x)⋅b(x)=(xn⋅(a_h)(x)+(a_l)(x))⋅(xn⋅(b_h)(x)+(b_l)(x))=x2*(a_h)(x)*(b_h)(x)+(a_l)(x)*(b_l)(x)+xk*(t-(a_h)(x)⋅(b_h)(x)-(a_l)(x)⋅(b_l)(x))
Если переписать без скобок с x:
Вычислим три многочлена:
a*b=(xn*(a_h)+(a_l))⋅(xn*(b_h)+(b_l))=x(2*n)*p+xn*(t-p-q)+q
Получается, мы заменили одно переножение многочленов размера 2*n на три перемножения многочленов размера n
Асимптотика
Умножение на xn, сложение и вычитание считаем выполнимыми за O(n). Получается, что мы разбили задачу на три задачи в два раза меньше, с затратами на объединение в O(n). Наши коэффициенты по мастер-теореме: a=3,b=2,c=1, а сложность алгоритма тогда будет: O(n(log_2)(3))