Для порівняння алгоритмів прийнято використовувати узагальнену характеристику, яка називається ефективністю. Говорять, що алгоритм Л, ефективнішеалгоритму А 2 ,якщо алгоритм Л виконується за менший час і (або) вимагає менше комп'ютерних ресурсів (оперативної пам'яті, дискового простору, мережного трафіку тощо).
Ефективний алгоритм повинен задовольняти вимоги прийнятного часу виконання та розумної ресурсомісткості, про що вже згадувалося в параграфі 1.1. Сукупність цих показників становить поняття складності алгоритму. При збільшенні часу виконання алгоритму та (або) задіяних ресурсів складність зростає. Таким чином, поняття ефективності та складності є зворотними один щодо іншого.
Характеристика алгоритму, що відображає тимчасові витрати на його реалізацію, називається тимчасовою складністю.Характеристика алгоритму, що відбиває комп'ютерні ресурсні витрати з його реалізацію, називається ємнісною складністю.
При кількісній та якісній оцінках алгоритму, пов'язаних з визначенням складності, використовують два підходи – практичний та теоретичний.
Практичний підхідпов'язаний з реально виконуваними алгоритмами на конкретних фізичних пристроях. Він характеризується параметрами, які можна виміряти та зафіксувати. Тимчасова складність при такому підході може виражатися в тимчасових одиницях (наприклад, мілісекундах) або кількості тактів процесора, що витрачаються на виконання алгоритму. Ємнісна складність може виражається в бітах (або інших одиницях вимірювання інформації), мінімальних апаратних вимогах, необхідних для виконання алгоритму, та ін.
Практична оцінка перестав бути абсолютним показником ефективності алгоритму. Кількісні значення, що отримуються при такому підході, залежать від багатьох факторів, таких як:
- технічні характеристикикомпонент, що становлять обчислювальну систему. Так, чим вище тактова частотароботи процесора, тим більше елементарних операцій за одиницю часу може бути виконано;
- характеристики програмного середовища (кількість запущених процесів, алгоритм роботи планувальника завдань, особливостей роботи операційної системиі т.д.);
- обраний мову програмування реалізації алгоритму. Програма, написана мовою високого рівня, швидше за все, буде виконуватися повільніше і вимагатиме більше ресурсів, ніж програма, написана низькорівневими мовами, які мають безпосередній доступ до апаратних ресурсів;
- досвід програміста, який реалізував алгоритм. Швидше за все, програміст-початківець напише менш ефективну програму, ніж програміст, що має досвід.
Таким чином, алгоритм, що виконується в одній і тій же обчислювальній системі для тих самих вхідних даних, може мати різні кількісні оцінки в різні моменти часу. Тому найважливішим виявляється теоретичний підхід до визначення складності.
Теоретична складністьхарактеризує алгоритм без прив'язки до конкретного обладнання, програмного забезпеченнята засобам реалізації. І тут тимчасова складність виявляється у кількості операцій, тактах роботи машини Тьюринга тощо. Ємнісна складність визначається обсягом даних (вхідних, проміжних, вихідних), кількістю задіяних осередків на стрічці машини Тиорінга і т.д.
При теоретичному підході до оцінки ефективності вважається, що алгоритм виконується на деякому ідеалізованому комп'ютері, котрій час виконання кожного виду операцій відомо і постійно. Також вважається, що ресурси такого комп'ютера нескінченні, тому ємнісну складність за теоретичного підходу зазвичай не визначають. Як тимчасову характеристику складності вибирають кількість інструкцій (операцій), що виконуються на ідеалізованому комп'ютері.
Кількісні оцінки, що отримуються при теоретичному підході, також можуть залежати від таких факторів:
- обсяг вхідних даних Чим він більший, тим більше часу потрібно виконання алгоритму;
- обраний метод розв'язання задачі. Наприклад, для великого обсягу вхідних даних алгоритм швидкого сортування ефективний, ніж алгоритм бульбашкового сортування, хоча і призводить до такого ж результату.
Час виконання алгоритму зазвичай залежить від обсягу вхідних даних (розмір входу), під яким розуміють розмірність задачі, що розв'язується. Так, при сортуванні множини значень обсяг даних становить кількість елементів цієї множини. Під час обробки рядків обсягом вхідних даних вважається довжина рядка.
Нехай п -обсяг вхідних даних деякого алгоритму. Позначимо за Т(п)кількість інструкцій, виконуваних на ідеалізованому комп'ютері під час виконання алгоритму, причому він визначається для «найгіршого випадку», коли обсяг операцій максимальний.
Поняття «найгіршого випадку» можна проілюструвати з прикладу. Нехай розглядається алгоритм перевірки наявності числового елемента в деякій множині (масиві) чисел. Якщо ця множина впорядкована за зростанням, то, взагалі кажучи, немає сенсу перевіряти елементи, розташовані після першого елемента, який більше шуканого. В цьому випадку Т(п)п. Однак у найгіршому випадку (для довільної несортованої множини) доведеться переглянути всі елементи множини. Очевидно, тут Т(п) = п.
Взагалі кажучи, Т(п)є деякою функцією від обсягу вхідних даних п.В багатьох випадках Т(п)виражається поліноміальною, статечною або логарифмічною функцією від п.
Поведінка величини Т(п)в залежності від збільшення пназивають асимптотичної складністюалгоритму. Кажуть що Т(п) має порядок складності 0(J(n))(читається «Провелике від/від п»)для деякого алгоритму, якщо є константа зта обсяг даних щтакі, що Уп > п 0і має місце нерівність Т(п) с/(п).
Цей факт записується як Т(п) = 0(J(n))і означає, що для функції Т(п)існують така функція f(n)і константа с, для яких, починаючи з деякого п 0 ,значення Т(п)не перевершує cf(n).
Функція f(n)являє собою верхню межу значень функції Т(п).Нехай, наприклад, Т(п) = 2п А + п 2 .Вибравши значення п 0= 0 і з = 5, для будь-якого п > п 0маємо Т(п) = 2п А + п 2Т(п) має порядок I 4 .
Функція Т(п) пов'язана з певним алгоритмом, тому часто кажуть, що порядок складності 0(/(п))має саме алгоритм.
Кажуть що Т(п)має нижній кордон Q(g(n))(читається «омега велика від gвід /г»), якщо існують константа з і обсяг даних п 0такі, що /пі має місце нерівність Т(п) > cg(n).
Цей факт записується як Т(п) = Q(g(n)).Нехай, наприклад, Т(п) = 2я 4 + п 2 .Вибравши значення з = 1, для будь-якого пмаємо Т(п)= 2я 4 + п 2 > сп А >отже, Т(п) має нижню межу я 4 .
Неважко бачити, що порядок і нижня межа не є єдиними для певної функції Т(п).У прикладах вище як /(я) можна було вибрати я 5 , я 6 ,..., а як g(n) -я 3 , я 2 ,.... Зазвичай як / (я) вибирають функцію з мінімальним ступенем, а як g(n)- З максимальною.
Порядок складності 0(/(я)) та нижня межа Q(g(rc)) є класами функцій. Інтуїтивно Q(g"(n)) можна розуміти як клас функцій зростаючих принаймні так само швидко, як і Т(п).Аналогічно, інтуїтивно 0(f(n))можна розуміти як клас функцій, що ростуть не швидше, ніж Т(п). Зпрактичної точки зору при оцінці складності алгоритму найбільш важливим виявляється саме клас функцій 0(f(n)).Визначення виду функції / (я) і є основним завданням розрахункутеоретичної складності алгоритму
Для будь-якого алгоритму щодо ступеня зростання можна скористатися такими властивостями 0(/(я)):
1) 0(kf(ji))= 0(/(я)), де k= Const. Таким чином, постійний множник у функції не впливає на швидкість зростання. Наприклад,
2) 0(J(ri)"g(n)) = 0(J(n))"0(g(ri)).Таким чином, порядок добутку двох функцій дорівнює добутку їх складнощів. Наприклад,
Іноді цю властивість записують як
3) 0(/(п) + g(n))дорівнює домінанті(функції з максимальним ступенем) функцій / (я) та g(n).Наприклад,
Теоретично складності алгоритмів виділяють такі класи функцій складності:
- 1) константна складність 0(1). Час роботи алгоритму та ресурси не мають залежності від обсягу вхідних даних. Зазвичай таку складність мають алгоритми, що не містять циклів та рекурсивних викликів;
- 2) лінійна складність 0(п).Зазвичай таку складність мають завдання, у яких кожен елемент вхідних даних має бути оброблений певну кількість разів, ніяк не пов'язану з кількістю обробок інших елементів;
- 3) логарифмічна складність 0(log 2 w), 0(nog 2 n).Іноді використовуються інші підстави логарифму;
- 4) поліноміальна складність 0(я 2), 0(/г 3), 0(я 4),...;
- 5) експоненційна складність 2 п, 3",....
У разі збільшення розміру входу складність кожного наступного типу функцій зростає швидше, ніж попереднього (крім 0(log 2 /?)). Для більшого обсягу вхідних даних краще використовувати алгоритми з меншою складністю.
При кількісному підрахунку складності спочатку вибирають операцію чи групу операцій, яка значима при цьому алгоритму (становить його основу). Як їх зазвичай виступають операції порівняння і арифметичні операції. До операцій порівняння відносять перевірку значень двох величин (менше, більше, одно, менше або одно, більше або одно, не дорівнює). Вони вважаються еквівалентними за часом виконання. Арифметичні операції, у свою чергу, поділяють на адитивніі мультиплікативні.До перших (часто званих просто додаванням)відносять додавання, віднімання, зменшення або зменшення значення лічильника. До других (званих просто множенням)відносять множення, розподіл, взяття залишку за модулем.
Операції додавання виконуються швидше, ніж операції множення, тому алгоритми з меншою кількістю множень є кращими, навіть якщо кількість додавань зростає пропорційно кількості зменшення множення.
Операції цілочисленного множення або розподілу па ступінь числа 2 відносять до адитивних операцій, так як при роботі з осередками пам'яті вони зводяться до зсуву, який еквівалентний операції складання.
Після вибору значних операцій вони поділяються на дві категорії:
- 1) операції, які безпосередньо впливають на складність алгоритму;
- 2) операції, що становлять «накладні витрати» при виконанні алгоритму (наприклад, виділення пам'яті для зберігання проміжних даних).
Безпосередній підрахунок чи оцінка кількості виконуваних операцій дозволяє оцінити Т(п).
Для оцінки порядку складності можна використати аналіз програмного кодуреалізує алгоритм. При цьому:
- алгоритми без циклів та рекурсивних викликів мають складність порядку 0(1). Таким чином, операції присвоєння, введення та виведення даних, умовні конструкціїмають константну складність;
- якщо дві частини програмного коду мають складності 0(J ((ri))і 0(J 2 (n)),то послідовне виконання має складність
- якщо тіло циклу виконується один раз для кожного елемента вхідних даних, складність виконання циклу має порядок 0(п)0( 1) = 0(п);
- порядок складності виконання вкладених циклів обчислюється за правилом твору 0(J x (n) f 2 (n)) = 0(/,(/?))- 0(J 2 (ri)).Якщо кожен із них має складність порядку 0(п),виконання вкладених циклів має складність порядку 0(п 2).
Приклад 1.3
Визначити порядок складності алгоритму програми мовою
Pascal, наведеного у лістингу 1.2. Рядки програми пронумеровані як коментарі (див. параграф 2.6).
Лістинг 1.2
(01) for i:=l to n do
(02) begin
(03) write("Введіть елемент масиву
з індексом "i,": ");
(04) Readln (MyArray [i]);
(05) end;
(06) for i:=l to n do
(07) for j:=1 to n do
(08) begin
(09) write("Введіть елемент масиву
з індексами ", i, ",", j, ":");
(10) Readln (МуDArray);
(11) end;
Рішення
Рядки 02, 05, 08, 11 не містять операторів, що виконуються, тому при визначенні порядку вони не враховуються.
Рядки 03 та 04 мають порядок 0(1). Послідовне виконання має порядок 0(1) + 0(1) = 0(1). Аналогічно, послідовне виконання рядків 09 та 10 має складність 0(1).
Цикл у рядках 01-05 має складність порядку О(п),вкладені цикли у рядках 06-11 - порядку 0(п 2).Підсумкова складність алгоритму має порядок
Оцінка складності алгоритму як тимчасової, так і ресурсної дозволяє визначити максимальний і середній час виконання алгоритму. Це дуже важливо при обробці великих масивів інформації, особливо у завданнях сортування та пошуку, розглянутих далі.
Для вирішення однієї і тієї ж задачі часто можна вигадати більше одного алгоритму. У зв'язку з чим виникає питання: який з алгоритмів “краще”?
Найчастіше, “краще”, певне, такий алгоритм, що у тих самих вхідних даних дійшов вирішення завдання, споживаючи меншу кількість обчислювальних ресурсів (пам'яті та часу). Це, звісно, несуворе міркування. Для більш суворого міркування введемо кілька понять.
Обчислювальний процес алгоритму це послідовність кроків, пройдена у виконанні алгоритму деяких вхідних даних.
Важливо розуміти різницю між самим алгоритмом та обчислювальним процесом, що породжується цим алгоритмом. Перший є тільки описомдругого.
Тимчасова складність алгоритму це час (T), необхідне для завершення обчислювального процесу алгоритму для деяких вхідних даних.
Зрозуміло, що час виконання залежить від конкретного виконавця. Скажімо, електронний калькулятор і суперкомп'ютер, ймовірно, виконуватимуть той самий алгоритм різний час.
Однак можна час (T) виразити через кількість елементарних дій (k) і середній час виконання елементарної дії (t):
При цьому \(k\) є властивістю самогоалгоритму, а (t) – властивістю виконавця.
Зважаючи на те, що (t) можна вважати константою для даного виконавця, зазвичай складність алгоритмів оцінюється з точністю до константного множника. Іншими словами, складність алгоритму оцінюється порядком зростання.
Порядок зростання позитивно-визначена функція \(g(x)\) має порядок зростання \(f(x)\) (записується \(g(x)=\mathcal(O)(f(x))\) ), якщо \(\exists c>0: \: \forall x>x_0, \, g(x) \leq c f(x)\).
Залежно від вхідних даних алгоритм може виконуватися різний час. Зазвичай оцінюється середняскладність та складність в гіршому випадку. Також є залежність від кількостівхідних даних (n) . Зазвичай оцінюється саме порядок зростання від (n).
Так, наприклад, читання даних та збереження їх у пам'яті у вигляді масиву буде мати складність \(\mathcal(O)(n)\) , або лінійну складність, а множення матриць вже кубічну\(\mathcal(O)(n^3)\) .
Крім часової складності алгоритму, важливою виявляється так само простороваскладність алгоритму.
Просторова складність алгоритму ця кількість додатковоюпам'яті (S), яке алгоритм вимагає для роботи. Пам'ять (D), необхідна для зберігання вхідних даних, не включається в (S).
\(S\) у випадку теж залежить від виконавчого устрою. Скажімо, якщо два виконавчі пристрої підтримують цілі довжиною 4 і 8 байт відповідно, то просторова складність алгоритму на 8-байтних цілих буде вдвічі більша, ніж на 4-байтних цілих. Тому просторова складність оцінюється так само порядком зростання.
Класи складності алгоритмів
Виділяються певні класи складності: це категорії, які мають схожу складність
Вирізняють такі основні класи складності:
DTIME Машина Тьюринга знаходить рішення задачі за кінцевий час (кількість кроків). Часто уточнюється асимптотика алгоритму, скажімо, якщо порядок зростання часу роботи \(T(n) = \mathcal(O)(f(n))\) , то вказують \(DTIME(f(n))\) . P Машина Тьюринга знаходить рішення завдання поліноміальний час (кількість кроків), тобто. \(T(n) = \mathcal(O)(n^k)\) , де \(k\in \mathbb(N)\) . \(P=DTIME(n^k)\) EXPTIME Машина Тьюринга знаходить вирішення завдання за експоненційний час (кількість кроків), тобто. \(T(n) = \mathcal(O)(2^(n^k))\)де \(k\in \mathbb(N)\) . \(EXPTIME=DTIME(2^(n^k))\) . DSPACE Машина Тьюринга знаходить рішення задачі, використовуючи кінцеву кількість додаткової пам'яті (осередків). Часто уточнюється асимптотика алгоритму, скажімо, якщо порядок зростання споживання пам'яті \(S(n) = \mathcal(O)(f(n))\) , то вказують \(DSPACE(f(n))\) . L Машина Тьюринга знаходить рішення задачі з логарифмічною просторовою складністю, тобто \(S(n) = \mathcal(O)(\log n)\). \ (L = DSPACE (log n) \) . PSPACE Машина Тьюринга знаходить рішення задачі з поліноміальною просторовою складністю, тобто \(S(n) = \mathcal(O)(n^k)\) , де \(k\in \mathbb(N)\) . \(PSPACE=DSPACE(n^k)\) . EXPSPACE Машина Тьюринга знаходить рішення задачі з експоненційною просторовою складністю, тобто \(S(n) = \mathcal(O)(2^(n^k))\)де \(k\in \mathbb(N)\) . \(EXPSPACE=DSPACE(2^(n^k))\) .
Крім того, існують теоретичні класи складності, які оперують поняттям недетерменованоюмашини Т'юрінга (НМТ). Їх визначення збігаються з наведеними вище, із заміною машини Тьюринга на НМТ, а назви мають префікс N (наприклад NP), крім NTIME і NSPACE, де D замінюється на N.
НМТ – це суто теоретична побудова, яка за принципами дії аналогічна МТ, з тією відмінністю, що для кожного зі станів може бути кілька можливих дій. При цьому НМТ завжди вибирає з можливих дій те, що приводить до рішення за мінімально можливу кількість кроків. Еквівалентно, НМТ здійснює обчислення всіхгілок і вибирає ту гілку, яка приводить до рішення за мінімально можливу кількість кроків.
Іноді можна почути, що квантові комп'ютери є НМТ. Хоча це може здаватися вірним у деяких випадках, у загальному випадку НМТ є більш потужною системоюніж квантовий комп'ютер.
Відомо що \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE\)
Крім того, \(P \subsetneq EXPTIME\) , \(NP \subsetneq NEXPTIME\) , \(PSPACE \subsetneq EXPSPACE\)
Також відомо, якщо \(P = NP\) , то \(EXPTIME = NEXPTIME\) .
Питання рівності P і NP одна із головних невирішених питань сучасної інформатики.
Приклади алгоритмів
Наведемо кілька прикладів простих алгоритмів та розглянемо їхню складність.
Зведення в цілий ступінь
Цей алгоритм був описаний у Стародавній Індії ще до нашої ери і використовується для обчислення натурального ступеня. речового числа\(x\)
- Записати \(n\) в двійковій системічислення
- Замінити в цьому записі кожну з 1 парою букв КХ, а кожен 0 – буквою К
- Викреслити крайню ліву пару КХ
- Читаючи отриманий рядок зліва направо, зустрічаючи букву К звести результат квадрат, а зустрічаючи букву X – помножити результат на x. Спочатку результат дорівнює x.
У цьому алгоритмі ми маємо число операцій множення, що дорівнює кількості цифр у двійковому поданні \(n\) у кращому випадку, і \(2(n-1)\) у гіршому випадку. У будь-якому випадку, тимчасова складність.
Додаткову пам'ять у ефективній реалізації алгоритму практично не потрібно, і вона не залежить від вхідних даних, тому просторова складність \(S(n) = \mathcal(O)(1)\) .
Слід зазначити, що є ефективніші алгоритми. Однак у порівнянні з “наївною” реалізацією, що вимагає ((mathcal(O)(n)) операцій множення, цей алгоритм порівняно ефективний.
Примноження цілих
Цей алгоритм множення називають іноді російським чи селянським, хоча він був відомий ще у Стародавньому Єгипті.
Перший множник послідовно множиться на два, а другий – ділиться націло на 2. Результати записуються у два стовпчики, доки у другому не вийде 1.
Результатом множення є сума чисел першого стовпчика, навпроти яких стоять непарні числа другого стовпчика.
Оскільки цілий розподіл і множення на 2 можна реалізувати зрушенням, цей алгоритм дає (2 \ log_2 n \) операцій зсуву, де (n) - менше з двох чисел. У гіршому випадку так само виходить (log_2 n - 1) операцій складання. У будь-якому випадку, тимчасова складність \(T(n) = \mathcal(O)(\log n)\).
Для ефективної реалізації алгоритму додаткової пам'яті практично не потрібно, і вона не залежить від вхідних даних, тому \(S(n) = \mathcal(O)(1)\)
Знову ж таки, слід зазначити, що існують ефективніші алгоритми. Однак у порівнянні з “наївною” реалізацією, що вимагає (mathcal(O)(n)) операцій складання, цей алгоритм порівняно ефективний.
приклад
Множення 23 на 43.
Візьмемо 23 як другий множник.
| 43 | 23 | непарне |
| 86 | 11 | непарне |
| 172 | 5 | непарне |
| 344 | 2 | |
| 688 | 1 | непарне |
Результат (43 +86 +172 +688 = 989 \)
Отримали 10 операцій зсуву та 4 операції складання. Для довідки \(\log_2(23) \approx 4.52\) .
Для будь-якого програміста важливо знати основи теорії алгоритмів, оскільки саме ця наука вивчає загальні характеристикиалгоритмів та формальні моделі їх подання. Ще з уроків інформатики нас вчать складати блок-схеми, що згодом допомагає при написанні складніших завдань, ніж у школі. Також не секрет, що практично завжди існує кілька способів вирішення того чи іншого завдання: одні припускають витратити багато часу, інші ресурсів, а треті допомагають лише наближено знайти рішення.
Завжди слід шукати оптимум відповідно до поставленого завдання, зокрема, розробки алгоритмів розв'язання класу завдань.
Важливо також оцінювати, як поводитиметься алгоритм при початкових значеннях різного обсягу та кількості, які ресурси йому знадобляться і скільки часу піде на виведення кінцевого результату.
Цим займається розділ теорії алгоритмів – теорія асимптотичного аналізу алгоритмів.
Пропоную в цій статті описати основні критерії оцінки та навести приклад оцінки найпростішого алгоритму. На Хабрахабрі вже є про методи оцінки алгоритмів, але вона орієнтована переважно на учнів ліцеїв. Цю публікацію можна вважати поглибленням цієї статті.
Визначення
Основним показником складності алгоритму є час, необхідне вирішення завдання та обсяг необхідної пам'яті.
Також при аналізі складності для класу завдань визначається деяке число, яке характеризує певний обсяг даних – розмір входу.
Отже, можемо зробити висновок, що складність алгоритму- Функція розміру входу.
Складність алгоритму може бути різною при тому самому розмірі входу, але різних вхідних даних.
Існують поняття складності в гіршому, середньомуабо найкращому випадку. Зазвичай оцінюють складність у гіршому випадку.
Тимчасова складністьу гіршому випадку – функція розміру входу, що дорівнює максимальній кількості операцій, виконаних під час роботи алгоритму під час вирішення завдання даного розміру.
Ємнісна складністьу гіршому випадку – функція розміру входу, рівна максимальній кількості осередків пам'яті, яких було звернення під час вирішення завдань даного розміру.
Порядок зростання складності алгоритмів
Порядок зростання складності(або аксіоматична складність) описує приблизну поведінку функції складності алгоритму при великому розмірі входу. З цього випливає, що з оцінці тимчасової складності немає необхідності розглядати елементарні операції, досить розглядати кроки алгоритму.
Крок алгоритму- Сукупність послідовно-розташованих елементарних операцій, час виконання яких не залежить від розміру входу, тобто обмежена зверху деякою константою.
Види асимптотичних оцінок
O – оцінка для найгіршого випадку
Розглянемо складність f(n) > 0, функцію того ж порядку g(n) > 0, розмір входу n > 0.
Якщо f(n) = O(g(n))і існують константи з > 0, n 0 > 0, то
0 < f(n) < c*g(n),
для n > n 0.
Функція g(n) у разі асимптотично-точна оцінка f(n). Якщо f(n) – функція складності алгоритму, порядок складності визначається як f(n) – O(g(n)).
Цей вираз визначає клас функцій, які ростуть не швидше, ніж g(n) з точністю до константного множника.
Приклади асимптотичних функцій
| f(n) | g(n) |
|---|---|
| 2n 2 + 7n - 3 | n 2 |
| 98n*ln(n) | n*ln(n) |
| 5n + 2 | n |
| 8 | 1 |
Ω – оцінка для кращого випадку
Визначення схоже на визначення оцінки для гіршого випадку, однак
f(n) = Ω(g(n)), якщо
0 < c*g(n) < f(n)
Ω(g(n))визначає клас функцій, які ростуть не повільніше, ніж функція g(n)з точністю до константного множника.
Θ – оцінка для середнього випадку
Варто лише згадати, що у цьому випадку функція f(n)при n > n 0всюди знаходиться між c 1 * g (n)і c 2 * g (n), де c - Константний множник.
Наприклад, при f(n) = n 2 + n; g(n) = n 2.
Критерії оцінки складності алгоритмів
Рівномірний ваговий критерій (РВК)передбачає, кожен крок алгоритму виконується одну одиницю часу, а осередок пам'яті одну одиницю обсягу (з точністю до константи).
Логарифмічний ваговий критерій (ЛВК)враховує розмір операнда, який обробляється тією чи іншою операцією та значення, що зберігається в комірці пам'яті.
Тимчасова складність при ЛВКвизначається значенням l(O p), де O p- Величина операнда.
Ємнісна складність при ЛВКвизначається значенням l(M), де M- Величина осередку пам'яті.
Приклад оцінки складності при обчисленні факторіалу
Необхідно проаналізувати складність алгоритму обчислення факторіалу. Для цього напишемо на псевдокоді мови С дане завдання:
Void main() ( int result = 1; int i; const n = ...; for (i = 2; i<= n; i++) result = result * n; }
Тимчасова складність при рівномірному ваговому критерії
Досить просто визначити, що розмір входу цієї задачі – n.
Кількість кроків – (n - 1).
Таким чином, тимчасова складність при РВК дорівнює O(n).
Тимчасова складність при логарифмічному ваговому критерії
У цьому пункті слід виділити операції, які слід оцінити. По-перше, це операції порівняння. По-друге, операції зміни змінних (додавання, множення). Операції присвоювання не враховуються, оскільки передбачається, що вона відбувається миттєво.
Отже, у цій задачі виділяється три операції:
1) i<= n
На i-му кроці вийде log(n).
Оскільки кроків (n-1), складність цієї операції складе (n-1) * log (n).
2) i = i + 1
На i-му кроці вийде log(i).
.
3) result = result * i
На i-му кроці вийде log((i-1)!).
Таким чином, виходить сума 
.
Якщо скласти всі значення і відкинути доданки, які свідомо ростуть повільніше зі збільшенням n, отримаємо кінцевий вираз 
.
Ємнісна складність при рівномірному ваговому критерії
Тут все просто. Необхідно підрахувати кількість змінних. Якщо задачі використовуються масиви, за змінну вважається кожен осередок масиву.
Оскільки кількість змінних не залежить від розміру входу, складність дорівнюватиме. O(1).
Ємнісна складність при логарифмічному ваговому критерії
У цьому випадку слід враховувати максимальне значення, яке може перебувати в осередку пам'яті. Якщо значення не визначено (наприклад, при операнді i > 10), вважається, що існує якесь граничне значення V max.
У цьому завдання існує змінна, значення якої перевищує n(i), та змінна, значення якої не перевищує n! (result). Таким чином, оцінка дорівнює O(log(n!)).
Висновки
Вивчення складності алгоритмів досить цікаве завдання. На даний момент аналіз найпростіших алгоритмів входить до навчальних планів технічних спеціальностей (якщо бути точним, узагальненого напряму «Інформатика та обчислювальна техніка»), які займаються інформатикою та прикладною математикою у сфері IT.
На основі складності виділяються різні класи завдань: P, NP, NPC. Але це не проблема теорії асимптотичного аналізу алгоритмів.
Функція складності 0(1). У алгоритмах константної складності більшість операцій у програмі виконуються чи кілька разів. Будь-який алгоритм, який завжди вимагає (незалежно від розміру даних) одного й того ж часу, має константну складність.
Функція складності 0(N).Час роботи програми зазвичай лінійний, коли кожен елемент вхідних даних потрібно обробити лише лінійне число разів. Ця функція складності характеризує простий цикл.
Функція складності 0(N 2), 0(N 3), 0(№) - поліноміальна функція складності: кількість операцій зростає пропорційно квадрату N.У випадку може бути О(Л^) залежно від складності завдання. Ця функція складності характеризує складний цикл.
Функція складності O(Log 2 (A0), 0(N log 2 (A0). Такий час працюють алгоритми, які ділять велику проблему на безліч невеликих, а потім вирішивши їх об'єднують рішення.
Функція складності 0(e N).Алгоритми з експоненційною складністю найчастіше виникають у результаті підходу, що називається методом грубої сили.
Функція складності 0(М) -кількість операцій зростає пропорційно факторіалу N.
Програміст повинен вміти проводити аналіз алгоритмів та визначати їхню складність. Тимчасова складність алгоритму може бути підрахована, виходячи з аналізу його керуючих структур.
Алгоритми без циклів та рекурсивних викликів мають константну складність. Якщо немає рекурсії та циклів, всі керуючі структури можуть бути зведені до структур константної складності. Отже, весь алгоритм також характеризується константної складністю. Визначення складності алгоритму в основному зводиться до аналізу циклів та рекурсивних викликів.
Наприклад, розглянемо алгоритм обробки елементів масиву.
For /": = 1 to N do Begin
Складність цього алгоритму Про(А), оскільки тіло циклу виконується А раз, і складність тіла циклу дорівнює 0(1). Якщо один цикл вкладено в інший і обидва цикли залежать від розміру однієї і тієї ж змінної, то вся конструкція характеризується квадратичною складністю.
For /: = 1 to N do For j: = 1 to N do Begin
Складність цієї програми 0(N 2).
приклад 1.Оцінимо складність програми, що вводить з клавіатури масив і знаходить у ньому найбільший елемент. Алгоритм складається з наступних кроків:
- - введення масиву (треба прочитати А елементів);
- - пошук найбільшого елемента (треба зробити А – 1 порівняння);
- - Висновок результату (треба вивести одне чи рядок).
Складемо число операцій А + (А – 1) + 1 = 2А, тобто. існує
така константа, що за будь-якого А кількість операцій вбирається у СА. Отже, складність алгоритму дорівнює 0(A).
приклад 2.Оцінимо складність програми, що вводить з клавіатури масив і знаходить у ньому елемент із заданою властивістю (наприклад, рівний певному значенню). Алгоритм складається з наступних кроків:
- - Введення масиву (аоперацій введення);
- - пошук елемента із заданим властивістю (елемент може бути як ближче до початку масиву, і у самому кінці; якщо елемента немає, необхідно зробити все А порівнянь, щоб у цьому переконатися);
- - Висновок результату.
У кращому разі зазначений алгоритм вимагатиме А + 2 операції (введення всього масиву, єдине порівняння, висновок), у гіршому (коли такого елемента немає, 2А + 1 операцію). Якщо А буде більшим числом, наприклад порядку 106, то одиницею можна знехтувати. Отже, складність алгоритму дорівнює 0(N).
приклад 3.Визначимо функцію складності алгоритму шифрування слова завдовжки Lметодом підстановки. Нехай існує таблиця, в якій для кожного символу алфавіту записано символ, який його треба замінити. Позначимо число букв алфавіту S.Алгоритм складається з наступних кроків:
- - Введення слова (одна операція);
- - Організація циклу:
- 1) для кожного символу знайти його заміну в таблиці (якщо таблиця не впорядкована і не має якихось властивостей, що полегшують пошук, то в гіршому випадку знадобиться Sоперацій для одного символу, якщо елемент знаходиться в самому кінці);
- 2) виведення знайденого символу;
- - Кінець циклу.
Загальна кількість операцій 1 + (S+)L.У разі досить великих Sі Lодиницями можна знехтувати, і вийде, що функція складності наведеного алгоритму є O(S L).
приклад 4.Визначимо функцію складності алгоритму перекладу натурального числа 1 V до двійкову систему числення (без операцій введення та виведення даних). Алгоритм складається з наступних кроків:
- - Цикл, поки результат розподілу числа на 2 не стане рівним 0:
- - Розділити число на 2 і запам'ятати залишок;
- - Прийняти результат поділу за нове число;
- - Кінець циклу.
Загальна кількість операцій не перевищує 1 + log 2 A. Тому описаний алгоритм має складність 0(og 2 N).
