Определение порядка числа вызовов

 

Числа Фибоначчи удовлетворяют отношению

где , т.е.

 

Сложность этого алгоритма – это .

 

Как ускорить?

 

Проблема в том, что мы много раз повторно вычисляем значение функции от одних и тех же аргументов.

 

Третий вопрос: можно ли ускорить алгоритм?

 

Вводим добавочный массив.

 

int fibo(int n)

{

const int MAXN = 1000;

static int c[MAXN];

if (n == 0) return 0;

if (n == 1) return 1;

if (c[n] > 0) return c[n];

return c[n] = fibo(n-1) + fibo(n-2);

}

 

Дерево вызовов модифицированной функции для n = 5

 

 

Проблема с представимостью данных

 

Значение функции растёт слишком быстро, и уже при небольших значениях n число выйдет за пределы разрядной сетки.

 

В реальных программах имеются ограничения на операнды машинных команд.

 

X86, X64 -> int есть 32 бита, longlong есть 64 бита.

 

X86: сложение 32-битных ≈ 1 такт, сложение 64-битных ≈ 3 такта.

X64: сложение 32-битных ≈ 1 такт, сложение 64-битных ≈ 1 такт.

 

X86: умножение 32-битных ≈ 3-4 тактов, умножение 64-битных ≈ 15-50 тактов.

X64: умножение 32-битных ≈ 3-4 такта, умножение 64-битных ≈ 4-5 тактов.

 

Как работать с длинными числами?

 

На 32-битной архитектуре сложение двух 64-разрядных -> сложение младших разрядов и прибавление бита переноса к сумме старших разрядов. Три машинных команды.

 

Числа (n) – те, которые занимают ровно n элементарных типов.

 

int – числа (1), longlong – числа (2).

 

Большие числа требуют представления в виде массивов из элементарных типов.

 

Сколько операций потребуется для сложения двух чисел (n)?

 

Как умножать длинные числа?

 

Школьный алгоритм: O(n²)

 

Алгоритм быстрого умножения

 

Можно ли быстрее?

 

Да. Используя принцип разделяй и властвуй.

 

Быстрый алгоритм умножения был изобретён Гауссом в 19 веке и переизобретён Анатолием Карацубой в 1960-м году.

 

Разделим число (n) на две примерно равные половины:

N₁ = Tx₁ + y₁

N₂ = Tx₂ + y₂

 

При умножении в столбик N₁ × N₂ = T²x₁x₂ + T (x₁y₂ + x₂y₁) + y₁y₂

 

Это – четыре операции умножения и три операции сложения.

 

Число T определяет, сколько нулей нужно добавить к концу числа в соответствующей системе счисления.

 

Алгоритм Карацубы

 

Алгоритм Карацубы находит произведение по другой формуле:

 

N₁ × N₂ = T²x₁x₂ + T (x₁ + y₁)(x₂ + y₂) - x₁x₂ - y₁y₂) + y₁y₂

N₁ = 56, N₂ = 78, T = 10

x₁ = 5, y₁ = 6

x₂ = 7, y₂ = 8

x₁x₂ = 5 × 7 = 35

(x₁ + y₁) (x₂ + y₂) = (5 + 6) (7 + 8) = 11 ∗ 15 = 165

y₁y₂ = 6 × 8 = 48

N₁ × N₂ = 35 ∗ 100 + (165 - 35 - 48) ∗ 10 + 48 = 4368

 

Т.е. 3 операции умножения и 6 сложения.

 

Основная теорема о рекурсии

Оценка асимптотического времени алгоритма

 

Как определить, какой порядок сложности будет иметь рекурсивная функция, не проводя вычислительных экспериментов?

 

Рекурсия – разбиение задачи на подзадачи с последующей консолидацией результата.

 

Пусть:

1) a – количество подзадач;

2) размер каждой подзадачи уменьшается в b раз и становится ;

3) сложность консолидации пусть – это O(n^d).

 

Время работы такого алгоритма, выраженное рекуррентно – это

 

Основная теорема о рекурсии

 

Пусть для некоторых a > 0, b > 1, d ≥ 0. Тогда

 

 

Оценка сложности алгоритма Карацубы

 

Коэффициент порождения задач a = 3.

 

Коэффициент уменьшения размера подзадачи b = 2.

 

Консолидация решения производится за время O(n) -> d = 1

 

Так как 1 < log₂3, то это третий случай теоремы -> сложность алгоритма – это

 

Операция умножения чисел (n) при умножении в столбик имеет порядок сложности O(n²).

 

Много операций сложения -> при малых N выгоднее “школьный” алгоритм.

 

Ещё о сложности

Введём вектор-столбец , состоящий их двух элементов последовательности Фибоначчи, и умножим его справа на матрицу :

 

Для вектора-столбца из элементов F_n-1 и F_n умножение на ту же матрицу даст:

 

Таким образом,

 

Возведение в степень

 

Для нахождения n-го числа Фибоначчи достаточно вычислить

 

Можно ли возвести число в n-ую степень за число операций, меньших n - 1?

 

Быстрое вычисление степеней

 

Возведение в квадрат – это умножение на себя.

 

х¹⁶ = (х⁸)² = ((х⁴)²)² = (((х²)²)²)²

 

х¹⁸ = (х⁹)² = ((х⁸ * х)²)² = (((х²)²)² * х)²

 

Рекуррентная формула

 

Рекурсивная функция быстрого умножения

 

SomeType – некий тип данных.

 

SomeType pow(SomeType x, int n)

{

if (n == 0) return (SomeType)1;

if (n % 2! = 0) return pow(x, n-1) * x;

SomeType y = pow(x, n/2);

return y*y;

}

 

Оценка сложности быстрого умножения

 

25 = 11001₂

 

n – нечётное -> обнуление последнего разряда.

 

n – чётное -> вычёркивание последнего разряда.

 

Каждую из единиц требуется уничтожить, не изменяя количества разрядов.

 

Каждый из разрядов требуется уничтожить, не изменяя количества единиц.

 

Сложность – O(log N).

⇐ Предыдущая1234

Поделиться: