Приближённое вычисление сложности

 

Пусть F(N) – функция сложности алгоритма в зависимости от N.

Тогда если существует такая функция G(N) (асимптотическая функция) и константа C, что

то сложность алгоритма F(N) определяется функцией G(N) с коэффициентом амортизации C.

 

Асимптотика основных зависимостей

 

Класс сложности определяется по асимптотической зависимости F(N).

 

Экспонента с любым коэффициентом превосходит любую степень.

 

Степень с любым коэффициентом, большим единицы, превосходит логарифм по любому основанию, большему единицы.

 

Логарифм по любому основанию, большему единицы превосходит 1.

 

F(N) = N³ + 7N² - 14N = ϴ (N³)

 

F(N) = 1.01^N + N¹⁰ = ϴ (1.01^N)

 

F(N) = N^1.3 + 10log₂N = ϴ (N^1.3)

 

На практике чаще используют O-нотацию, так как ϴ -нотацию обычно сложнее доказывать.

 

Зависимость времени исполнения от исходных данных

 

Пусть имеется массив A длиной N элементов.

Сколько операций потребуется, чтобы обнаружить номер первого вхождения элемента со значением P алгоритмом, заключающимся в последовательном просмотре элементов массива?

 

K_min = 1

 

K_max = N

 

 

Подходит ли символ ϴ?

 

Нет. Для данного алгоритма подходит O-символ: f(N) = O(N).

 

 

Пусть имеется массив A длиной N элементов.

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

 

K = N

 

Подходит ли символ ϴ?

 

Подходит. f(N) = ϴ (N).

 

Неполиномиальные задачи. Задача о рюкзаке

 

Имеется N предметов, каждый из которых имеет объём V_i и стоимость C_i, предметы неделимы. Имеется рюкзак вместимостью V. Требуется поместить в рюкзак набор предметов максимальной стоимости, суммарный объём которых не превышает объёма рюкзака.

 

Задача о рюкзаке

 

Обратим внимание на то, что предметы разрезать на куски нельзя. Если это разрешить, то задача будет иметь простое решение.

 

Для решения задачи достаточно перебрать все возможные комбинации из N предметов. Это гарантирует то, что мы не пропустим нужной комбинации.

 

Для определения количества комбинаций можно рассуждать так, что K предметов можно выбрать из N предметов (C_N^K), и так для всех K от 0 до N.

 

F(N) = (1 + 1) ^N = 2^N

 

Одно из решений задачи о рюкзаке

 

1) перенумеруем все предметы;

2) установим максимум стоимости в 0;

3) составим двоичное число с N разрядами, в котором единица в разряде будет означать, что предмет выбран для укладки в рюкзак (расстановку);

4) рассмотрим все расстановки, начиная от 000... 000 до 111... 111, для каждой из них подсчитаем значение суммарного объёма:

4.1) если суммарный объём расстановки не превосходит объёма рюкзака, то подсчитывается суммарная стоимость и сравнивается с достигнутым ранее максимумом стоимости;

4.2) если вычисленная суммарная стоимость превосходит максимум, то максимум устанавливается в вычисленную стоимость и запоминается текущая конфигурация.

 

Свойства алгоритма

 

Предложенный алгоритм:

1) детерминированный;

2) конечный;

3) массовый;

4) полезный.

Его сложность пропорциональна 2^N, так как требуется перебрать все возможные комбинации предметов.

 

Сложность решения задачи о рюкзаке

 

Много ли времени потребуется на решение задачи для N = 128?

 

Предположим, на подсчёт одного решения потребуется 10^-9 секунд, т.е. одна наносекунда.

Предположим, задачу будет решать триллион компьютеров (10¹²).

Тогда общее время решения задачи будет составлять

 

NP-задачи о рюкзаке

 

Задача о рюкзаке относится к классу NP-полных. Быстрое (полиномиальное) точное решение таких задач (пока) не найдено. Если будет найдено решение одной из NP-полных задач, то будут решены все задачи из этого класса. Сейчас их решают приближённо.

 

Исполнитель алгоритма

Исполнители

 

Нашим исполнителем будет язык C++.

 

Элементарные типы отображаются на вычислительную систему char, int, double.

 

Элементарные операции аппаратного исполнителя: операции над элементарными типами и операции передачи управления.

 

Типы данных языка – комбинация элементарных типов данных.

 

Операции языка – комбинация элементарных операций.

 

⇐ Предыдущая1234Следующая ⇒

Поделиться: