Добрый день, мои дорогие гвардейцы. Сюда вы зашли, наверняка, по одно простой причине: скоро или уже настала контрольная по сложностям алгоритмов. Мда, соглашусь с вами, вещь весьма и весьма специфичная на вкус, но и с этим отпрыском Нургла поможет нам справиться свет Его. Скачивайте файл и читайте Истину.
Задание 1
Найти асимптотическую оценку временнóй сложности рекурсивного алгоритма.
Ключевое слово тут «временная», потому не нужно сразу искать постоянную. Вами дадут задание такого вида (разбиение на фиксированное число подзадач равного размера): {1}

Разберем, что тут есть:
n – изначальный размер задачи
1 – количество подзадач данного алгоритма в рекурсии
2 – показатель уменьшения размера подзадач по отношению к основной задаче
3 – показатель нерекурсивной части, то есть какая сложность у нерекурсивной части алгоритма
4 – конечное условие выхода из задачи
Обозначим 1, как a. 2 как b. 3 как f(n) – поскольку там целая функция стоит.
Тогда в данным случае легко получить ответ с помощью основной теоремы:
Посчитаем p=logba. Для данного случая будет p=log55 = 1. Теперь нужно сравнить две части: np и f(n), очевидно что может быть 3 случая (не рассматриваем, когда теорема неприменима):
— np>f(n) тогда очевидно оценка станет по наибольшему из чисел T(n) = Ɵ(np)
— np=f(n) значит должно быть некое «усреднение» которым станет логарифм
T(n) = Ɵ(np∙logn)
— np<f(n) похоже на первый случай, берем по большему из чисел T(n) = Ɵ(f(n))
Вернемся к нашему примеру:

Но учтите, сравнивать нужно не просто числа, а их «сложности» и разница роста должна быть полиномиально разной (если без сложных слов – степени должны быть различными). То есть для данного случая np хоть и не равен f(n), но и не растет быстрее или медленнее, соответственно ответом будет «не подходит ни под один из случаев основной теоремы.
Когда еще у нас может возникнуть ответ: «Не подходит ни под один из случаев»? Всего в нескольких ситуациях:
- a ≠ const, как например в примере: {2}

- a<1 {9}

- f(n)<0 {10}

- У f(n) нет условия регулярности, например если f(n)=n3*sin(n)
Решим еще несколько примеров: {3}

a = 16, b = 4 → p=log416=2
f(n) = n2-3n, сложность f(n) берется просто по наибольшей степени, если слагаемых несколько, то есть O(f(n))=n2
В данном случае: np=n2=f(n), это второй случай теоремы, то есть ответом будет T(n) = Ɵ(n2∙logn) {4}

a = 7, b = 2 → p=log27, f(n) = 11n2+2, что приводится к n2, то есть решение задачи сводится к:

очевидно что log27>2, соответственно левая часть растет полиномиально быстрее правой, что приводит нас к первому случаю теоремы и ответ будет

Но все таки для некоторых «каверзных» случаев решение существует, а именно таких случаев два:
- Аддитивное разбиение {5}

Для него решением будет: {6}

- Квадратичное разбиение {7}

Для него решение: {8}

Разберем и на них парочку задач {11}

Как видно тут квадратичное разбиение, причем a = 1, соответственно это будет первый случай квадратичного разбиения. {13}

Тут разбиение аддитивное и a=1, соответственно это первый случай теоремы, причем d=1.
Задание 2
Точная оценка сложности рекурсивного алгоритма.
Вот тут, мои дорогие, и начнется самый ад, что Кадия покажется райским местом. По факту, как повезет с заданием и если не повезет, как не повезло мне, то придется не брать формулу из методички, а выводить самому, либо формула будет очень замороченной =)
Но это будет как дополнительный материал, который я напишу, если вы очень прям захотите, а пока что оценим более общий случай:

Для него решением будет такое разложение:

Причем, если у нас не одна, а несколько нерекурсивых частей вида c·nd, то каждой из них будет соответствовать своя форма выделенная красным в решении.
Для лучшего понимания решим такую задачку:

Сразу «распихаем» все коэффициенты:
a=4, b=2 → p = log24 = 2
f(n) = n3+6n, что разбивается на две части: f1(n)=n3 и f2(n)=6n
Для f1: с1 = 1, d1 = 3 → 4≠23
Для f2: c2 = 6, d2 = 1 → 4≠21
К сожалению пример не слишком нагляден, поскольку два раза у нас появилось только второй пункт, но не суть. В таком случае у нас будет такая формула:

Задание 3
Задача на формулу Акра-Баззи. В отличие от всех предыдущих задач – тут все просто и понятно. Одна формула – одно решение. Распишем же ее:
Пусть дана задача вида:

Зачастую вам будут встречаться они именно с двумя рекурсивными слагаемыми. Общее решение будем таким:

Где n’ я обычно беру 0 или 1, чтобы красиво сократить все, там можно взяь любую константу
А p – является решением уравнения:

Решим и на этот метод задачку:

Сначала найдем чиселку p:

Далее считаем S:

Как можно заметить, я попросту подставил вместо n’ – 0, чтобы оно нам не мешало в конечных вычислениях 😉
И наконец-то завершительный этап, подставляем в итоговое выражение:

И тут вы спросите, а почему я вот так вот взял и выкинул пару слагаемых? Все очень просто, мы считаем ассимптотику, а не точную сложность. В таком виде подсчета под нож пускаются все слагаемые меньших порядков, чем максимальное, а так же убираются все константные множители (но не константы, если они являются высшей степенью)
Всем хорошего настроения и хорошо написать работу. Помните, Император поможет только тому, кто сам старается что-то сделать.