Асимптотичний аналіз - Студопедія

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

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

Основні оцінки зростання, що зустрічаються в асимптотичному аналізі:

·Ο(О-велике) - верхня асимптотична оцінка зростання тимчасової функції;

· Ω (Омега) – нижня асимптотична оцінка зростання тимчасової функції;

· Θ (Тета) – нижня та верхня асимптотичні оцінки зростання тимчасової функції.

Нехайn- величина обсягу даних. Тоді зростання функції алгоритмуf(n) можна обмежити функційg(n) асимптотично:

Позначення	Опис
f(n) ÎΟ(g(n))	fобмежена зверху функцієюgз точністю до постійного множника
f(n) Î Ω(g(n))	fобмежена знизу функцієюgз точністю до постійного множника
f(n) Θ(g(n))	fобмежена знизу та зверху функцієюg

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

Під фразою «складність алгоритму єΟ(f(n))» мається на увазі, що зі збільшенням обсягу вхідних данихn, часроботи алгоритму зростатиме не швидше ніж деяка константа, помножена наf(n).

Важливі правила асимптотичного аналізу:

1.O(k*f) =O(f) - постійний множникk(константа) відкидається, оскільки зі зростанням обсягу даних, його сенс втрачається, наприклад:

2.O(f*g) =O(f)*O(g) - оцінка складності добутку двох функцій дорівнює добутку їх складнощів, наприклад:

3.O(f/g)=O(f)/O(g) – оцінка складності частки двох функцій дорівнює частці їх складнощів, наприклад:

4.O(f+g) дорівнює домінантіO(f) таO(g) – оцінка складності суми функцій визначається як оцінка складності домінанти першого та другого доданків, наприклад:

Підрахунок кількості операцій - справа стомлива і, що важливо, зовсім не обов'язкова. Виходячи з вище перерахованих правил, щоб визначити складність алгоритму, не потрібно, як ми це робили раніше, вважати всі операції, достатньо знати, якою складністю володіє та чи інша конструкція алгоритму (оператор або група операторів). Так, алгоритм, який не містить циклів і рекурсій, має константну складністьO(1). Складність циклу, що виконуєnітерацій, дорівнюєO(n). Конструкція їх двох вкладених циклів, що залежать від однієї і тієї ж змінноїn, має квадратичну складністьO(n2 ).

Ось найпоширеніші класи складності:

·O(1) – константна складність;

·О(n) – лінійна складність;

·О(n a) – поліноміальна складність;

·Про(log(n)) –логарифмічна складність;

· O(n*log(n)) – квазілінійна складність;

·O(2n) – експоненційна складність;

·O(n!) – факторіальна складність.

Чи не знайшли те, що шукали? Скористайтеся пошуком:

Вимкніть adBlock! і оновіть сторінку (F5)дуже потрібно

---