У цьому підручнику ви дізнаєтесь, що таке асимптотичні позначення. Крім того, ви дізнаєтесь про позначення Big-O, позначення Theta та позначення Omega.
Ефективність алгоритму залежить від кількості часу, пам’яті та інших ресурсів, необхідних для виконання алгоритму. Ефективність вимірюється за допомогою асимптотичних позначень.
Алгоритм може не мати однакової продуктивності для різних типів входів. Зі збільшенням розміру вводу продуктивність буде змінюватися.
Дослідження зміни продуктивності алгоритму із зміною порядку вхідного розміру визначається як асимптотичний аналіз.
Асимптотичні позначення
Асимптотичні позначення - це математичні позначення, що використовуються для опису часу роботи алгоритму, коли вхідні дані прагнуть до певного значення або граничного значення.
Наприклад: При сортуванні за допомогою міхура, коли вхідний масив вже відсортований, час, який забирає алгоритм, є лінійним, тобто найкращим випадком.
Але коли вхідний масив знаходиться в зворотному стані, алгоритм займає максимальний час (квадратичний) для сортування елементів, тобто найгіршого випадку.
Коли введений масив не відсортований, ані в зворотному порядку, тоді потрібно середній час. Ці тривалості позначаються за допомогою асимптотичних позначень.
В основному є три асимптотичні позначення:
- Позначення Big-O
- Омега-позначення
- Позначення тета
Позначення Big-O (O-notation)
Позначення Big-O представляє верхню межу часу роботи алгоритму. Таким чином, це дає найгіршу складність алгоритму.
Big-O дає верхню межу функції
O (g (n)) = (f (n): існують позитивні константи c і n 0 такі, що 0 ≦ f (n) ≦ cg (n) для всіх n ≧ n 0 )
Вищезазначений вираз можна описати як функцію, яка f(n)належить множині, O(g(n))якщо існує позитивна константа, cтака, що вона лежить між 0і cg(n), при досить великій n.
Для будь-якого значення nчас роботи алгоритму не перетинає час, передбачений O(g(n)).
Оскільки він надає найгірший час роботи алгоритму, він широко використовується для аналізу алгоритму, оскільки нас завжди цікавить найгірший сценарій.
Омега-позначення (Ω-позначення)
Позначення омега представляє нижню межу часу роботи алгоритму. Таким чином, це забезпечує найкращу складність алгоритму.
Омега дає нижню межу функції
Ω (g (n)) = (f (n): існують позитивні константи c і n 0 такі, що 0 ≦ cg (n) ≦ f (n) для всіх n ≧ n 0 )
Вищезазначений вираз можна описати як функцію, що f(n)належить множині, Ω(g(n))якщо існує позитивна константа, cтака, що вона лежить вище cg(n), для досить великого n.
Для будь-якого значення n, мінімальний час, необхідний алгоритму, задається Omega Ω(g(n)).
Позначення тета (Θ-позначення)
Позначення тета включає функцію зверху та знизу. Оскільки він представляє верхню та нижню межі часу роботи алгоритму, він використовується для аналізу середньої складності алгоритму.
Тета обмежує функцію в межах факторів констант
Для функції g(n), Θ(g(n))задається співвідношенням:
Θ (g (n)) = (f (n): існують позитивні константи c 1 , c 2 і n 0 такі, що 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) для всіх n ≧ n 0 )
Вищезазначений вираз можна описати як функцію, яка f(n)належить до множини, Θ(g(n))якщо існують позитивні константи і така, що її можна затиснути між і , при досить великому n.c1c2c1g(n)c2g(n)
Якщо функція f(n)лежить де-небудь між ними і для всіх , тоді кажуть, що вона асимптотично тісно пов'язана.c1g(n)c2g(n)n ≧ n0f(n)
