Дослідження ефективності розроблених алгоритмів. Поняття складності та ефективності алгоритмів і структур даних Від чого залежить ефективність алгоритму

Дата створення: 2009-03-25 12:50:48
Останній раз внесено зміни: 2012-02-08 6:29:55

Дана стаття - вступна в розділі "Алгоритми".

В даному розділі ми зосередимося на двох напрямках: структури даних і безпосередньо алгоритми.

З деякими структурами даних Ви вже познайомилися: масиви, структури, класи. Це приклади статичних структур даних. Тобто задали ми спочатку програми десять елементів масиву, в кінці програми цих елементів так і залишилося десять. На сторінках розсилки і в даному розділі ми познайомимося динамічними структурами даних. Деякі з цих структур просто роблять програмістську життя легше, без інших неможливо побудувати певний алгоритм.

Також структур даних стосуються ще дві області програмування, які ми будемо розглядати: STL і D3DX. У STL (стандартна бібліотека шаблонів в C ++) зібрані математичні структури даних і алгоритми, а в D3DX (допоміжна бібліотека DirectX) присутній ряд цікавих нам структур, які безпосередньо використовуються в графічних додатках.

ефективність алгоритмів

В даному - вступному випуску ми не будемо розглядати будь-яку конкретну структуру. Тут ми поговоримо про ефективність алгоритмів. Для цього нам буде потрібно провести кілька понять.

Відразу хочу підкреслити, що в даній статті я свідомо спрощую матеріал. І з математичної точки зору, деякі визначення в даній статті не коректні. За більш точним і повним описомматематичних понять, вам буде потрібно звернутися до підручників з алгоритмами.

Приступимо. Є кілька критеріїв оцінки ефективності алгоритмів. Для простоти ми будемо обговорювати тільки тимчасову ефективність.

Здавалося б тимчасова ефективність повинна виражатися в секундах. Але в даному випадку це не так. тому що один і той же алгоритм на різних комп'ютерах виконається за різну кількість часу.

Розглянемо приклад: у нас є масив з десяти елементів. І у нас є два алгоритму: пошук елемента в масиві і сортування масиву.

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

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

Що у нас тут є? Перш за все розмір вхідних даних. Позначимо його - n. З нашого прикладу n = 10.

Так ось, ефективність алгоритму - це функція залежить від розміру вхідних даних. Чим більше вхідних даних, тим довше буде виконуватися алгоритм.

Функція в математичному контексті і в програмістські розуміється приблизно однаково. Є відмінності, але поки вони для нас несуттєві.

При виконанні алгоритму для кожного вхідного значення виконується якась базова операція. В алгоритмі пошуку - це просте порівняння. При сортуванні базова операція складніше. Базова операція теж впливає на ефективність алгоритму.

В даному прикладі ефективність алгоритму зручно розуміти не як функцію, а як цикл. Дивіться: у нас є набір вхідних даних в кількості n. n- це кількість повторень циклу. А базова операція - це тіло циклу.

порядок зростання

Тепер нам потрібно розглянути залежність зміни кількості базових операцій необхідних для виконання алгоритму від збільшення розміру вхідних даних.

Приклад: у нас є упорядкований масив з 10 елементів. Уявімо, що нам потрібно знайти два числа. Під час пошуку виявилося, що перше число знаходилося в середині масиву, а друге - в кінці. Тепер візьмемо масив з 20 елементів (в два рази більше). І знову, елементи розташовані так, що перший елемент виявився в середині, а другий в кінці. Ці два випадки мають однаковий порядок зростання: при збільшенні розміру вхідних даних в два рази, кількість базових операцій необхідних для виконання алгоритму збільшилася в два рази.

Примітка: зауважте, що хоча ми і використовуємо один алгоритм в прикладі, але розглядаємо два випадки виконання цього алгоритму. В даному контексті ми можемо говорити про двох різних алгоритмах. Це важливо!

Тепер переходимо до найважливішого в статті.

Порівняння порядків зростання

Кількість базових операцій за яке виконується алгоритм - це час виконання алгоритму. Позначимо його як t (n).

І позначимо якусь проста функція g (n)з якої ми будемо порівнювати час виконання t (n).

Для порівняння порядків зростання двох алгоритмів використовують межа відносини часу виконання двох алгоритмів.

При постійному збільшенні nми обчислюємо відношення t (n)до g (n).

У першому випадку t (n)має менший порядок зростання. При збільшенні розміру вхідних даних, знаменник буде рости набагато швидше чисельника. Відповідно чим більше n, Тим результат буде ближче до нуля.

У другому випадку порядок зростання t (n)і g (n)однаковий. з- якась константа. Тобто при збільшенні розміру вхідних даних, наскільки виріс порядок зростання t (n)настільки ж виріс і порядок зростання g (n).

У третьому випадку t (n)має більший порядок зростання. Відповідно результат прямує до нескінченності.

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

Цілі і завдання лекції: ознайомлення з методами аналізу складності та ефективності алгоритмів і структур даних

Основні питання: експериментальний і аналітичний аналіз ефективності алгоритмів.

Класичне твердження Н.Вірта «Гарна програма - це єдність продуманого алгоритму і ефективних структур даних».

аналіз алгоритмів
Поняття "алгоритму і структур даних" є центральними в сфері комп'ютерних технологій, однак, щоб називати деякі структури даних і алгоритми «якісними та ефективними», слід використовувати точні прийоми їх аналізу. В якості природного критерію якості природничо виділити, по-перше, час виконання. Також важливим є обсяг витрачених ресурсів пам'яті і дискового простору, швидкості доступу до даних (ефективність структури даних). Увага також слід приділити надійності і достовірності рішень, їх стабільності.

Алгоритм не повинен бути прив'язаний до конкретної реалізації. В силу різноманітності використовуваних засобів програмування різні в реалізації алгоритми можуть видавати відрізняються по ефективності результати.

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

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

Після того як буде отримано набір оцінок, можна побудувати графік і провести його апроксимацію.

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

В цілому можна сказати, що час виконання алгоритму або методу структури даних зростає в міру збільшення розміру вихідних даних, хоча воно залежить і від типу даних, навіть при рівному розмірі. Крім того, час виконання залежить від апаратного забезпечення (процесора, тактової частоти, розміру пам'яті, місця на диску і ін.) І програмного забезпечення (операційного середовища, мови програмування, компілятора, інтерпретатора і ін.), За допомогою яких здійснюється реалізація, компіляція і виконання алгоритму. Наприклад, при всіх інших рівних умовах час виконання алгоритму для певної кількості вихідних даних буде менше при використанні більш потужного комп'ютера або під час запису алгоритму у вигляді програми на машинному коді в порівнянні з його виконанням віртуальною машиною, яка проводить інтерпретацію в байт-коди.

Висновок, що проведення аналізу алгоритмів емпіричним шляхом не є дійсно надійним. Основні недоліки можна звести до наступних трьох положень:

1) експерименти можуть проводитися лише з використанням обмеженого набору вихідних даних; результати, отримані з використанням іншого набору, не враховуються.

2) для порівняння ефективності двох алгоритмів необхідно, щоб експерименти по визначенню часу їх виконання проводились на однаковому апаратному та програмному забезпеченні;
3) для експериментального вивчення часу виконання алгоритму необхідно провести його реалізацію і виконання.

Таким чином, ми приходимо до необхідності використання для аналізу алгоритмів методів загального аналізу, який дозволяє:

1) враховує різні типивхідних даних;

2) дозволяє здійснювати оцінку відносної ефективності будь-яких двох алгоритмів незалежно від апаратного та програмного забезпечення;

3) може проводитися за описом алгоритму без його безпосередньої реалізації або експериментів.

Суть загального аналізу полягає в тому, що певним алгоритмом ставиться у відповідність функція f = f (n1, .., nm). У найпростішому варіанті це функція однієї змінної n1 - кількості вихідних даних. Однак можуть бути і інші змінні - наприклад точність розрахунку або його достовірність. Так для визначення того чи є певна кількість простим в разі великих чисел (довжина двійкового представлення більш ніж 200 біт) використовують імовірнісний метод, достовірність якого можна варіювати. Найбільш відомі функції це лінійні, статечні, логарифмічні. Тому слід витратити час і згадати основи роботи з ними.

При побудові алгоритмів перша стадія йде з використанням не мова програмування, а опису на людській мові. Подібні описи не є програмами, але разом з тим вони більш структуровані, ніж звичайний текст. Зокрема, «високорівневі» опису поєднують природну мову і поширені структури мови програмування, що робить їх доступними і в той же час інформативними. Такі описи сприяють проведенню високорівневого аналізу структури даних або алгоритму. Подібні описи прийнято називати псевдокодом. Слід також зазначити, що для проведення аналізу псевдокод є часто більш корисним, ніж код на конкретній мові програмування.

Іноді виникає необхідність довести якісь твердження у відношенні до певної структурі даних або алгоритму. Наприклад, потрібно продемонструвати правильність і швидкість виконання алгоритму. Для суворого докази тверджень необхідно використовувати математичний мову, який, послужить доказом або обґрунтуванням висловлювань. існує кілька простих способівподібного докази.

Іноді затвердження записуються в узагальненій формі: «Безліч s містить елемент х, що володіє властивістю v. Для доказу цього твердження достатньо навести приклад х "належить" s, який володіє даними властивістю. У подібній узагальненій формі записуються, як правило, і малоймовірні затвердження, наприклад: «Кожен елемент х безлічі s має властивість Р». Щоб довести помилковість цього твердження, досить просто навести приклад: х "належить" s, який не має властивість Р. В даному випадку елемент х виступатиме в якості контр-приклад.

приклад:Стверджується, що будь-яке число виду 2 ^ n - 1 є простим, якщо n - ціле число, більше 1. Затвердження помилково.

Доведення:щоб довести неправоту, обходимо знайти контр-приклад.

Такий контр-приклад: 2 ^ 4 - 1 = 15, 15 = 3 * 5.

Існує й інший спосіб, заснований на доказі від противного (використанні заперечення). Основними методами в даному випадку є контрапозиции і контрадікція. Використання методів протиставлення подібно дзеркального відображення: щоб довести, що «якщо x - істинно, то і y - істинно», будемо стверджувати зворотне «якщо y - помилково, то і x - хибно». З точки зору логіки, ці твердження ідентичні, проте другий вираз, яке є котропозіціей першого, більш зручно.

приклад:Якщо a * b - непарне число, то а - непарна або b - непарне.

Доведення:для доказу цього твердження розглянемо контрапозиции: «Якщо а - парне число і b - непарне, то a * b - парне. Нехай, а = 2 * x, для деякого цілого числа x. Тоді a * b = 2 * i * b, а отже твір a * b - парне.

При використанні методів докази від протилежного корисним є використання логіки.

A or b = слід дотримуватися a або b, або і a і b одночасно.
. a and b = потрібно одночасне виконання a і b.
. a xor b = слід дотримуватися a, але не b або ж b, але не a.

При використанні методу контрадікціі для доказу того, що твердження q - вірно, спочатку передбачається, що q - помилково, а потім показується, що таке припущення призводить до протиріччя (наприклад, 2 * 2<>4). Прийшовши до подібного протиріччя, можна стверджувати, що ситуації, при якій q - хибно, не існує, і, отже, q - істинно.

У більшості випадків в твердженнях про час виконання програми або використовуваному просторі застосовується цілочисельний параметр n (що означає «розміри» завдання). Тоді коли ми формулюємо твердження x (n), то для безлічі значень n подібні твердження рівносильні. Так як дане твердження відноситься до "нескінченного" безлічі чисел, неможливо провести вичерпне прямий доказ. У подібних ситуаціях використовують методи індукції. Метод індукції заснований на тому; що для будь-якого n> 1. Існує кінцева послідовність дій, яка починається чогось свідомо істинного і, в кінцевому підсумку, призводить до доказу того, що q (n) істинно. Таким чином, доказ за допомогою індукції починається з твердження, що q (n) істинно при n = 1,2,3 і т.д. до деякої константи k. Далі доводиться, що наступний «крок» індукції q (n + 1), q (n + 2) також є істинним для n> k.

При аналізі алгоритмів, підрахунку кількості операцій і часу їх виконання, не слід враховувати "дрібні деталі", слід нехтувати постійними множниками і константами. На практиці використовують поняття функції великого Про. припустимо, що існують дві функції f (n) і g (n), вважається, що f (n)<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

Наприклад, алгоритм підрахунку в масиві кількості елементів рівних нулю описується О (n), де n - кількість елементів.

1) 20n3 + 7,2n2-21,78n + 5 описується як О (n3)

2) xn-2 + a (0) описується як О (xn).

2) 3 * log (n) + log (log (n)) описується як О (log (n)).

3) 2100 описується як О (1)

4) 5 / n описується як О (1 / n).

Зверніть увагу на те, що функція o (n) обмежує зверху цільову функцію витрат часу, але необхідно прагнути завжди вибирати таку функцію О (n), щоб була максимальна точність.

Найбільш відомі функції О в порядку їх зростання:

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

Залежно від виду функції f (n) виділяють наступні класи складності алгоритмів.

Класи складності алгоритмів в залежності від функції трудомісткості
Вид f (n)	Характеристика класу алгоритмів
	Більшість інструкцій більшості функцій запускається один або кілька разів. Якщо все інструкції програми мають таку властивість, то час виконання програми постійно.
log N	Коли час виконання програми є логарифмічним, програма стає повільніше з ростом N. Таке час виконання зазвичай притаманне програмами, які зводять велику задачу до набору менших підзадач, зменшуючи на кожному кроці розмір завдання на деякий постійний фактор. Зміна підстави не сильно позначається на зміні значення логарифма: п
N	Коли час виконання програми є лінійним, це зазвичай означає, що кожен вхідний елемент піддається невеликий обробці.
N log N	Час виконання, пропорційне N log N, виникає тоді, коли алгоритм вирішує завдання, розбиваючи її на менші підзадачі, вирішуючи їх незалежно і потім об'єднуючи рішення.
N 2	Коли час виконання алгоритму є квадратичним, він корисний для практичного використання при вирішенні відносно невеликих завдань. Квадратичне час виконання зазвичай з'являється в алгоритмах, які обробляють всі пари елементів даних (можливо, в циклі подвійного рівня вкладеності).
N 3	Схожий алгоритм, який обробляє трійки елементів даних (можливо, в циклі потрійного рівня вкладеності), має кубічну час виконання і практично можна застосовувати лише для малих завдань.
2 N	Лише кілька алгоритмів з експоненціальним часом виконання має практичне застосування, хоча такі алгоритми виникають природним чином при спробах прямого рішення задачі, наприклад повного перебору.

На підставі математичних методів дослідження асимптотичних функцій трудомісткості на нескінченності виділені п'ять класів алгоритмів.

1. Клас швидких алгоритмів з постійним часом виконання, їх функція трудомісткості O (1). Проміжний стан займають алгоритми зі складністю O (log N), які також відносять до даного класу.

2.Класс раціональних або поліноміальних алгоритмів, функція трудомісткості яких визначається полиномиально від вхідних параметрів. Наприклад, O (N), O (N 2, O (N 3).

3.Класс субекспоненціальное алгоритмів зі ступенем трудомісткості O (N log N).

4.Класс експоненційних алгоритмів зі ступенем трудомісткості O (2 N).

5.Класс надекспоненціальних алгоритмів. Існують алгоритми з факторіальною трудомісткістю, але вони в основному не мають практичного застосування.

Стан пам'яті при виконанні алгоритму визначається значеннями, які вимагають для розміщення певних ділянок. При цьому в результаті виконання завдання може бути задіяно додаткову кількість осередків. Під обсягом пам'яті, необхідним алгоритмом А для входу D, розуміємо максимальну кількість елементів пам'яті, задіяних в ході виконання алгоритму. Ємнісна складність алгоритму визначається як асимптотична оцінка функції обсягу пам'яті алгоритму для гіршого випадку.

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

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

• Трудомісткість конструкції "Дотримання" є сума трудоемкостей блоків, що слідують один за одним: f = f 1 + f 2 + ... + f n.
• Трудомісткість конструкції "Галуження" визначається через ймовірність переходу до кожної з інструкцій, яка визначається умовою. При цьому перевірка умови також має певну трудомісткість. Для обчислення трудомісткості гіршого випадку може бути обраний той блок розгалуження, який має велику трудомісткість, для кращої нагоди - блок з меншою трудомісткістю. f if = f 1 + f then · p then + f else · (1-p then)
• Трудомісткість конструкції "Цикл" визначається обчисленням умови припинення циклу (зазвичай має порядок 0 (1)) і твори кількості виконаних ітерацій циклу на найбільше можливе число операцій тіла циклу. У разі використання вкладених циклів їх трудомісткості перемножуються.

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

1. Декомпозиція алгоритму передбачає виділення в алгоритмі базових конструкцій і оцінку і трудомісткості. При цьому розглядається дотримання основних алгоритмічних конструкцій.
2. Порядковий аналіз трудомісткості по базовим операціям мови має на увазі або сукупний аналіз (облік всіх операцій), або післяопераційний аналіз (облік трудомісткості кожної операції).
3. Зворотній композиція функції трудомісткості на основі методики аналізу базових алгоритмічних конструкцій для кращого, середнього і гіршого випадків.

Особливістю оцінки ресурсної ефективності рекурсивних алгоритмів є необхідність врахування додаткових витрат пам'яті і механізму організації рекурсії. Тому трудомісткість рекурсивних реалізацій алгоритмів пов'язана з кількістю операцій, які виконуються при одному рекурсивном виклик, а також з кількістю таких викликів. Враховуються також витрати на повернення значень і передачу управління в точку виклику. При оцінці необхідної пам'яті стека потрібно враховувати, що в конкретний момент часу в стеку зберігається не фрагмент рекурсії, а ланцюжок рекурсивних викликів. Тому обсяг стека визначається максимально можливим числом одночасно отриманих рекурсивних викликів.

У процесі вирішення прикладних задач вибір відповідного алгоритму викликає певні труднощі. Алгоритм повинен відповідати таким, що суперечить одне одному вимогам:

1) бути простим для розуміння, перекладу в програмний код і налагодження;

2) ефективно використовувати обчислювальні ресурси і виконуватися по можливості швидко.

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

Складність алгоритму - це величина, що відображає порядок величини необхідного ресурсу (часу або додаткової пам'яті) в залежності від розмірності задачі.

Таким чином, будемо розрізняти тимчасову T(n) І просторову (її також називають ємнісний) V(n) Складності алгоритму. При розгляді оцінок складності, будемо використовувати тільки тимчасову складність. Просторова складність оцінюється аналогічно.

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

1) временн ая складність алгоритму програми;

2) якість скомпільованої коду виконуваної програми в силу відмінностей в реалізації окремих операторів мови високого рівня з урахуванням «оптимізації» компілятора під конкретний процесор;

3) зовнішні затримки, викликані роботою операційної системи, наприклад, при реалізації механізму багатозадачності або інших програм, що працюють в «фоновому» режимі (наприклад, антивіруси);

4) машинні інструкції, які використовуються для виконання програми, які орієнтовані на апаратні особливості архітектури ЕОМ, наприклад, паралельну обробку лінійної послідовності даних.

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

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

Існує метод, що дозволяє теоретично оцінити час виконання алгоритму, який і розглянемо далі. Однак, даний підхід слід використовувати акуратно, так як він не враховує кількість виконуваних алгоритмом операцій, що не відносяться до основних. Крім того, це значення можна визначити тільки приблизно.

Часто, тимчасова складність алгоритму залежить від кількості вхідних даних. Зазвичай кажуть, що тимчасова складність алгоритму має порядок T(n) Від вхідних даних розміру n. Точно визначити величину T(n) На практиці представляється досить важко. Тому вдаються до асимптотическим відносинам з використанням O-сімволікі, яка дає прийнятну оцінку часу виконання алгоритму для не безкінечна великих і не нескінченно малих значень n. Вона також дозволяє відповісти на запитання на кшталт: «у скільки разів швидше буде працювати реалізація даного алгоритму на комп'ютері, швидкодія якого більше нашого, наприклад, в 10 разів»? Здавалося б, відповідь очевидна - в 10 разів. Однак, якщо O(n) = n(n+ 1) / 2, то це далеко не так. Або: «наскільки довше буде виконуватися програма, якщо подвоїти розмір вхідних даних»? Відповідь буде такою: приблизно в чотири рази повільніше.

Коли використовують позначення « O(×) », мають на увазі не точний час виконання, а тільки його межа зверху, причому з точністю до постійного множника. Коли говорять, наприклад, що алгоритму потрібен час порядку O(n 2), мають на увазі, що час виконання завдання зростає не швидше, ніж квадрат кількості елементів.

Наприклад, якщо число тактів (дій), необхідне для роботи алгоритму, виражається як 25 n 2 – 10n*log n + 5n+ 15, то це алгоритм, для якого T(n) Має порядок O(n 2). Фактично, з усіх доданків залишається тільки те, яке вносить найбільший внесок при великих n(В цьому випадку іншими складовими можна знехтувати), і ігнорується коефіцієнт перед ним.

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

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

1. максимальну складність T max(n), Або складність найбільш несприятливого випадку, коли алгоритм працює найдовше;

2. середню складність T mid(n) - складність алгоритму в середньому;

3. мінімальну складність T min(n) - складність в найбільш сприятливому випадку, коли алгоритм справляється швидше за все.

Кінець роботи -

Ця тема належить розділу:

Міністерство освіти Російської Федерації

Асимптотичні позначення асимптотично точна оцінка функції .. основні класи ефективності .. в теорії аналізу ефективності алгоритмів до одного класу відносять всі функції чий порядок зростання однаковий з точністю ..

Якщо Вам потрібно додатковий матеріал на цю тему, або Ви не знайшли те, що шукали, рекомендуємо скористатися пошуком по нашій базі робіт:

Що будемо робити з отриманим матеріалом:

Якщо цей матеріал виявився корисним ля Вас, Ви можете зберегти його на свою сторінку в соціальних мережах:

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

Пам'ять або час

Багато алгоритми пропонують вибір між обсягом пам'яті і швидкістю. Завдання можна вирішити швидко, використовую великий обсяг пам'яті, або повільніше, займаючи менший обсяг.
Типовим прикладом в даному випадку служить алгоритм пошуку найкоротшого шляху. Представивши карту міста у вигляді мережі, можна написати алгоритм для визначення найкоротшої відстані між двома будь-якими точками цієї мережі. Щоб не обчислювати ці відстані щоразу, коли вони нам потрібні, ми можемо вивести найкоротші відстані між усіма точками і зберегти результати в таблиці. Коли нам знадобиться дізнатися найкоротша відстань між двома заданими точками, ми можемо просто взяти готове відстань з таблиці.
Результат буде отриманий миттєво, але це зажадає величезного обсягу пам'яті. Карта великого міста може містити десятки тисяч точок. Тоді, описана вище таблиця, повинна містити більше 10 млрд. Осередків. Тобто для того, щоб підвищити швидкодію алгоритму, необхідно використовувати додаткові 10 Гб пам'яті.
З цієї залежності виникає ідея об'ємно-часової складності. При такому підході алгоритм оцінюється, як з точки зорі швидкості виконання, так і з точки зору спожитої пам'яті.
Ми будемо приділяти основну увагу тимчасової складності, але, тим не менш, обов'язково будемо оскаржувати і обсяг споживаної пам'яті.

оцінка порядку

При порівнянні різних алгоритмів важливо знати, як їх складність залежить від обсягу вхідних даних. Припустимо, при сортуванні одним методом обробка тисячі чисел займає 1 с., А обробка мільйона чисел - 10 с., При використанні іншого алгоритму може знадобитися 2 с. і 5 с. відповідно. В таких умовах не можна однозначно сказати, який алгоритм краще.
У загальному випадку складність алгоритму можна оцінити по порядку величини. Алгоритм має складність O (f (n)), якщо при збільшенні розмірності вхідних даних N, час виконання алгоритму зростає з тією ж швидкістю, що і функція f (N). Розглянемо код, який для матриці A знаходить максимальний елемент в кожному рядку.
for i: = 1 to N do
begin
max: = A;
for j: = 1 to N do
begin
if A> max then
max: = A
end;
writeln (max);
end;
У цьому алгоритмі змінна i змінюється від 1 до N. При кожній зміні i, змінна j теж змінюється від 1 до N. Під час кожної з N ітерацій зовнішнього циклу, внутрішній цикл теж виконується N раз. Загальна кількість ітерацій внутрішнього циклу одно N * N. Це визначає складність алгоритму O (N ^ 2).
Оцінюючи порядок складності алгоритму, необхідно використовувати тільки ту частину, яка зростає найшвидше. Припустимо, що робочий цикл описується виразом N ^ 3 + N. У такому випадку його складність буде дорівнює O (N ^ 3). Розгляд швидко зростаючої частини функції дозволяє оцінити поведінку алгоритму при збільшенні N. Наприклад, при N = 100, то різниця між N ^ 3 + N = 1000100 і N = 1000000 дорівнює всього лише 100, що становить 0,01%.
При обчисленні O можна не враховувати постійні множники в виразах. Алгоритм з робочим кроком 3N ^ 3 розглядається, як O (N ^ 3). Це робить залежність відносини O (N) від зміни розміру завдання більш очевидною.

визначення складності

Найбільш складними частинами програми зазвичай є виконання циклів і виклик процедур. У попередньому прикладі весь алгоритм виконаний за допомогою двох циклів.
Якщо одна процедура викликає іншу, то необхідно більш ретельно оцінити складність останньої. Якщо в ній виконується певний число інструкцій (наприклад, висновок на друк), то на оцінку складності це практично не впливає. Якщо ж в викликається процедурі виконується O (N) кроків, то функція може значно ускладнити алгоритм. Якщо ж процедура викликається всередині циклу, то вплив може бути набагато більше.
Як приклад розглянемо дві процедури: Slow зі складністю O (N ^ 3) і Fast зі складністю O (N ^ 2).
procedure Slow;
var
i, j, k: integer;
begin
for i: = 1 to N do
for j: = 1 to N do
for k: = 1 to N do
(Якась агресивна дія)
end;
procedure Fast;
var
i, j: integer;
begin
for i: = 1 to N do
for j: = 1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
Якщо у внутрішніх циклах процедури Fast відбувається виклик процедури Slow, то складності процедур перемножуються. В даному випадку складність алгоритму становить O (N ^ 2) * O (N ^ 3) = O (N ^ 5).
Якщо ж основна програма викликає процедури по черзі, то їх складності складаються: O (N ^ 2) + O (N ^ 3) = O (N ^ 3). Наступний фрагмент має саме таку складність:
procedure Slow;
var
i, j, k: integer;
begin
for i: = 1 to N do
for j: = 1 to N do
for k: = 1 to N do
(Якась агресивна дія)
end;
procedure Fast;
var
i, j: integer;
begin
for i: = 1 to N do
for j: = 1 to N do
(Якась агресивна дія)
end;
procedure Both;
begin
Fast;
Slow;
end;

Складність рекурсивних алгоритмів

проста рекурсія

Нагадаємо, що рекурсивними процедурами називаються процедури, які викликають самі себе. Їх складність визначити досить важко. Складність цих алгоритмів залежить не тільки від складності внутрішніх процедур, а й від кількості ітерацій рекурсії. Рекурсивна процедура може виглядати досить простий, але вона може серйозно ускладнити програму, багаторазово викликаючи себе.
Розглянемо рекурсивную реалізацію обчислення факторіала:
function Factorial (n: Word): integer;
begin
if n> 1 then
Factorial: = n * Factorial (n-1)
else
Factorial: = 1;
end;
Ця процедура виконується N раз, таким чином, обчислювальна складність цього алгоритму дорівнює O (N).

багаторазова рекурсія

Рекурсивний алгоритм, який викликає себе кілька разів, називається багаторазової рекурсією. Такі процедури набагато складніше аналізувати, крім того, вони можуть зробити алгоритм набагато складніше.
Розглянемо таку процедуру:
procedure DoubleRecursive (N: integer);
begin
if N> 0 then
begin
DoubleRecursive (N-1);
DoubleRecursive (N-1);
end;
end;
Оскільки процедура викликається двічі, можна було б припустити, що її робочий цикл буде дорівнює O (2N) = O (N). Але насправді ситуація набагато складніше. Якщо уважно дослідити цей алгоритм, то стане очевидно, що його складність дорівнює O (2 ^ (N + 1) -1) = O (2 ^ N). Завжди треба пам'ятати, що аналіз складності рекурсивних алгоритмів вельми нетривіальне завдання.

Об'ємна складність рекурсивних алгоритмів

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

Середній і найгірший випадок

Оцінка складності алгоритму до порядку є верхньою межею складності алгоритмів. Якщо програма має великий порядок складності, це зовсім не означає, що алгоритм буде виконуватися дійсно довго. На деяких наборах даних виконання алгоритму займає набагато менше часу, ніж можна припустити на основі їх складності. Наприклад, розглянемо код, який шукає заданий елемент у векторі A.
function Locate (data: integer): integer;
var
i: integer;
fl: boolean;
begin
fl: = false; i: = 1;
while (not fl) and (i<=N) do
begin
if A [i] = data then
fl: = true
else
i: = i + 1;
end;
if not fl then
i: = 0;
Locate: = I;
end;
Якщо шуканий елемент знаходиться в кінці списку, то програмі доведеться виконати N кроків. В такому випадку складність алгоритму складе O (N). У цьому найгіршому випадку час роботи алгоритму будемо максимальним.
З іншого боку, шуканий елемент може знаходиться в списку на першій позиції. Алгоритмом доведеться зробити всього один крок. Такий випадок називається найкращим і його складність можна оцінити, як O (1).
Обидва ці випадки малоймовірні. Нас найбільше цікавить очікуваний варіант. Якщо елемента списку спочатку безладно змішані, то шуканий елемент може виявитися в будь-якому місці списку. В середньому потрібно зробити N / 2 порівнянь, щоб знайти потрібний об'єкт. Значить складність цього алгоритму в середньому становить O (N / 2) = O (N).
В даному випадку середня і очікувана складність збігаються, але для багатьох алгоритмів найгірший випадок сильно відрізняється від очікуваного. Наприклад, алгоритм швидкого сортування в найгіршому випадку має складність порядку O (N ^ 2), в той час як очікувана поведінка описується оцінкою O (N * log (N)), що багато швидше.

Загальні функції оцінки складності

Зараз ми перерахуємо деякі функції, які найчастіше використовуються для обчислення складності. Функції перераховані в порядку зростання складності. Чим вище в цьому списку знаходиться функція, тим швидше буде виконуватися алгоритм з такою оцінкою.
1. C - константа
2. log (log (N))
3. log (N)
4. N ^ C, 0 5. N
6. N * log (N)
7. N ^ C, C> 1
8. C ^ N, C> 1
9. N!
Якщо ми хочемо оцінити складність алгоритму, рівняння якої складності якого містить кілька цих функцій, то рівняння можна скоротити до функції, розташованої нижче в таблиці. Наприклад, O (log (N) + N!) = O (N!).
Якщо алгоритм викликається рідко і для невеликих обсягів даних, то прийнятною можна вважати складність O (N ^ 2), якщо ж алгоритм працює в реальному часі, то не завжди достатньо продуктивності O (N).
Зазвичай алгоритми зі складністю N * log (N) працюють з хорошою швидкістю. Алгоритми зі складністю N ^ C можна використовувати тільки при невеликих значеннях C. Обчислювальна складність алгоритмів, порядок яких визначається функціями C ^ N і N! дуже велика, тому такі алгоритми можуть використовуватися тільки для обробки невеликого обсягу даних.
На закінчення наведемо таблицю, яка показує, як довго комп'ютер, який здійснює мільйон операцій в секунду, буде виконувати деякі повільні алгоритми.