Позначення Великого О, пояснене на прикладах

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

Що таке нотація Big O і як це працює?

Простіше кажучи, позначення Big O повідомляє вам кількість операцій, які зробить алгоритм. Свою назву він отримав від буквального «Великого О» перед передбачуваною кількістю операцій.

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

Big O встановлює найгірший час роботи

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

Ви знаєте, що для простого пошуку потрібно O (n) разів. Це означає, що в гіршому випадку вам доведеться шукати кожен запис (представлений n), щоб знайти Джейн.

Але коли ви запускаєте простий пошук, виявляєте, що записи Джейн - це перший запис у базі даних. Вам не потрібно переглядати кожен запис - ви знайшли його з першої спроби.

Цей алгоритм зайняв час O (n)? Або це зайняло час O (1), тому що ви знайшли записи Джейн із першої спроби?

У цьому випадку 0 (1) - найкращий варіант - вам пощастило, що записи Джейн були вгорі. Але позначення Big O фокусується на найгіршому сценарії, тобто 0 (n) для простого пошуку. Це запевнення в тому, що простий пошук ніколи не буде повільнішим за O (n) час.

Час роботи алгоритму зростає з різною швидкістю

Припустимо, що перевірка кожного елемента в базі даних шкільного округу займає 1 мілісекунду.

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

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

Якщо є 1 мільярд елементів, використання простого пошуку займе до 1 мільярда мс або 11 днів. З іншого боку, використання бінарного пошуку займе всього 32 мс у найгіршому випадку:

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

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

Позначення Big O показує кількість операцій

Як зазначалося вище, позначення Big O не відображає час роботи алгоритму. Натомість він показує кількість операцій, які він буде виконувати. Він повідомляє вам, як швидко росте алгоритм, і дозволяє вам порівняти його з іншими.

Ось декілька поширених алгоритмів та час їх роботи у нотації Big O:

Великі позначення OПриклад алгоритму
O (журнал n)Двійковий пошук
O (n)Простий пошук
O (n * log n)Швидкий сорт
O (n2)Сортування виділення
О (н!)Подорожній продавець

Тепер ви знаєте достатньо, щоб бути небезпечним із позначенням Big O. Вийдіть там і починайте порівнювати алгоритми.