Контрольная работа 2 «Сложности алгоритмов»

Добрый день, мои дорогие гвардейцы. Сюда вы зашли, наверняка, по одно простой причине: скоро или уже настала контрольная по сложностям алгоритмов. Мда, соглашусь с вами, вещь весьма и весьма специфичная на вкус, но и с этим отпрыском Нургла поможет нам справиться свет Его. Скачивайте файл и читайте Истину.

Задание 1

Найти асимптотическую оценку временнóй сложности рекурсивного алгоритма.

Ключевое слово тут «временная», потому не нужно сразу искать постоянную. Вами дадут задание такого вида (разбиение на фиксированное число подзадач равного размера): {1}

Разберем, что тут есть:

n – изначальный размер задачи

1 – количество подзадач данного алгоритма в рекурсии

2 – показатель уменьшения размера подзадач по отношению к основной задаче

3 – показатель нерекурсивной части, то есть какая сложность у нерекурсивной части алгоритма

4 – конечное условие выхода из задачи

Обозначим 1, как a. 2 как b. 3 как f(n) – поскольку там целая функция стоит.

Тогда в данным случае легко получить ответ с помощью основной теоремы:

Посчитаем p=log_ba. Для данного случая будет p=log₅5 = 1. Теперь нужно сравнить две части: n^p и f(n), очевидно что может быть 3 случая (не рассматриваем, когда теорема неприменима):

— n^p>f(n) тогда очевидно оценка станет по наибольшему из чисел T(n) = Ɵ(n^p)

— n^p=f(n) значит должно быть некое «усреднение» которым станет логарифм

 T(n) = Ɵ(n^p∙logn)

— n^p<f(n) похоже на первый случай, берем по большему из чисел T(n) = Ɵ(f(n))

Вернемся к нашему примеру:

Но учтите, сравнивать нужно не просто числа, а их «сложности» и разница роста должна быть полиномиально разной (если без сложных слов – степени должны быть различными). То есть для данного случая n^p хоть и не равен f(n), но и не растет быстрее или медленнее, соответственно ответом будет «не подходит ни под один из случаев основной теоремы.

Когда еще у нас может возникнуть ответ: «Не подходит ни под один из случаев»? Всего в нескольких ситуациях:

• a ≠ const, как например в примере: {2}

• a<1 {9}

• f(n)<0 {10}

• У f(n) нет условия регулярности, например если f(n)=n³*sin(n)

Решим еще несколько примеров: {3}

a = 16, b = 4 → p=log₄16=2

f(n) = n²-3n, сложность f(n) берется просто по наибольшей степени, если слагаемых несколько, то есть O(f(n))=n²

В данном случае: n^p=n²=f(n), это второй случай теоремы, то есть ответом будет T(n) = Ɵ(n²∙logn) {4}

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

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

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

• Аддитивное разбиение {5}

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

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

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

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

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

Тут разбиение аддитивное и a=1, соответственно это первый случай теоремы, причем d=1.

Задание 2

Точная оценка сложности рекурсивного алгоритма.

Вот тут, мои дорогие, и начнется самый ад, что Кадия покажется райским местом. По факту, как повезет с заданием и если не повезет, как не повезло мне, то придется не брать формулу из методички, а выводить самому, либо формула будет очень замороченной =)

Но это будет как дополнительный материал, который я напишу, если вы очень прям захотите, а пока что оценим более общий случай:

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

Причем, если у нас не одна, а несколько нерекурсивых частей вида c·n^d, то каждой из них будет соответствовать своя форма выделенная красным в решении.

Для лучшего понимания решим такую задачку:

Сразу «распихаем» все коэффициенты:

a=4, b=2 → p = log₂4 = 2

f(n) = n³+6n, что разбивается на две части: f₁(n)=n³ и f₂(n)=6n

Для f₁: с₁ = 1, d₁ = 3 → 4≠2³

Для f₂: c₂ = 6, d₂ = 1 → 4≠2¹

К сожалению пример не слишком нагляден, поскольку два раза у нас появилось только второй пункт, но не суть. В таком случае у нас будет такая формула:

Задание 3

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

Пусть дана задача вида:

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

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

А p – является решением уравнения:

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

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

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

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

И наконец-то завершительный этап, подставляем в итоговое выражение:

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

Всем хорошего настроения и хорошо написать работу. Помните, Император поможет только тому, кто сам старается что-то сделать.