Алгоритми і структури даних

Короткі теоретичні відомості

Питання для повторення

1. Використання формул у табличному процесорі. Абсолютні та відносні посилання.

Постановка задачі

У загальному випадку час роботи алгоритму збільшується зі збільшенням кількості вхідних даних, тому загальноприйнята практика — представляти час роботи програми як функцію, залежну від кількості вхідних елементів. Найбільш адекватне поняття розміру вхідних даних залежить від даної задачі: це може бути кількість вхідних елементів або загальна кількість бітів тощо.

Час роботи алгоритму для тих або інших вхідних даних вимірюється в кількості елементарних операцій, або "кроків", які необхідно виконати. Проте, як правило, при цьому не потрібна велика точність. Для досить великих вхідних даних сталі множники і доданки нижчого порядку, що фігурують у виразі для точного часу роботи алгоритму, пригнічуються ефектами, що викликані збільшенням розміру вхідних даних.

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

Як правило, алгоритм, ефективніший в асимптотичному  розумінні, буде більш продуктивним для всіх вхідних даних, за винятком дуже малих. Позначення, що використовуються для опису асимптотичної поведінки часу роботи алгоритму, використовують функції, область визначення яких — множина цілих невід’ємних чисел. Подібні позначення зручні для опису часу роботи T(n) в найгіршому випадку як функції, що визначена лише для цілих чисел, які є розміром вхідних даних.

У наближених формулах часто використовується символ O, за допомогою якого позначають асимптотичну верхню межу. Запис g(n)=O(f(n)) означчає, що існують такі додатні константи M і n₀, що g(n) ≤ Mf(n) для всіх цілих n ≥n₀.

Поліноміальним алгоритмом називається  алгоритм, у якого часова складність дорівнює
O(p(n)), де p(n) — поліном,  n — вхідна довжина. Алгоритми, часова складність яких не піддається вказаній оцінці, називають експоненціальними. Відмінність між поліноміальними й експоненціальними алгоритмами стає особливо помітною при розв'язуванні задач великого розміру.

Завдання для самостійного виконання

Постановка задачі

Скласти таблиці, які демонструють залежність часу роботи алгоритмів з різними функціями часової складності від розміру вхідних даних.

Хід роботи

1. Нехай для розміру n вхідних даних час роботи алгоритму дорівнює f(n) мікросекунд. Побудувати електронну таблицю для визначення часу роботи алгоритму (в секундах), для розмірів вхідних даних 10, 20, ..., 200 (константу для переведення мікросекунд у секунди запишіть у комірку A1, після чого використовуйте абсолютне посилання на цю комірку).

2. Варіант	f1(n)	f2(n)
   1	n	2n
   2	n2	3n
   3	n3	3n
   4	lgn	2n
   5	n1/2	2n

3. Користуючись побудованою у завданні 1 таблицею, для кожної з функцій f₁(n) і f₂(n) визначте максимальне значення n, для яких задача може бути розв'язана за час t, якщо t = 1 сек, 1 хв, 1 год, 1 день, 1 місяць, 1 рік, 1 століття.
4. Користуючись у завданні 1 таблицею, визначте, як змінить масимальне значення n, для яких задача може бути розв'язана за 1 сек при збільшенні швидкодії у 100 разів, у 1000 разів.
5. На комп'ютері зі швидкодією 10 000 оп/с реалізується алгоритм, виконання якого вимагає виконання 100lgn  операцій, де n — розмір вхідних даних. Алгоритм, реалізований на комп'ютері з швидкодією 100 000 000 оп/с, вимагає виконання n² операцій. Скласти таблицю, що відображає залежність часу роботи алгоритмів від кількості n чисел (n=1000, 2000, ..., 20000). Побудуйте графіки залежностей в одній системі координат.

Запитання для самоконтролю

1. Чому при дослідженні часової складності алгоритмів користуються, як правило, асимптотичними позначеннями?
2. Що означає символ O?
3. Які алгоритми називаються поліноміальними? експоненціальними?