Складність алгоритмів, зведення задач, нижні оцінки складності задач

Час, який витрачається алгоритмом, як функція розміру задачі, називається часовою складністю цього алгоритму. Гранична поведінка цієї складності при збільшені розміру задачі називається асимптотичною часовою складністю.

Аналогічно, можна виділити об’ємну складність та асимптотичну об’ємну складність.

Оцінки складності:

· верхні оцінки: ;

· нижні оцінки: ;

· ефективні оцінки: ;

Позначенням визначаються функції, нехтувано малі у порівнянні з функцією . Вони визначаються умовою .

Зведення задач. Метод зведення використовується для встановлення оцінки складності однієї задачі за відомою оцінкою складності іншої задачі.

Нехай маємо задачу та задачу . Кажуть, що задача та перетворюється (зводиться) до задачі , якщо:

1. Початкові дані задачі перетворюються на відповідні початкові дані задачі .

2. Розв’язується задача .

3. Розв’язок задачі (вихідні дані) перетворюється у правильний розв’язок задачі .

Якщо кроки 1 та 3 можна виконати за час , де – розмір задачі , то кажуть, що задача є -звідною до задачі . Цей факт позначають так: .

Зводимість не є симетричним відношенням. Якщо задачі та взаємно звідні, то вони називаються еквівалентними.

Нижні оцінки методом перетворення: Якщо відомо, що задача вимагає щонайменше часу, і , то задачу можна розв’язати за час не менший за .

Верхні оцінки методом перетворення: Якщо відомо, що задачу можна розв’язати за час , і , то задачу можна розв’язати за час, який не перевищує .

Відомі нижні оцінки складності деяких задач:

· Для скінченної -елементної множини перевірка умови вимагає часу ;

· Для впорядкування сукупності з елементів необхідно часу ;

· Якщо деяка задача у -вимірному просторі вимагає часу, то для цієї ж задачі розмірністью також потрібно принаймні часу;

· Задачі із нижньою оцінкою складності :

o перевірка того, чи є у заданій сукупності два рівних елементи;

o перевірка включення множин;

o перевірка перетину множин;

o перевірка на значимість: дано точок на площині, визначити, чи усі вони належать опуклій оболонці;

o перевірка -близькості: чи є серед елементів заданої -елементної множини два елементи, які знаходяться на відстані .