Нотація Big O

11.1 Визначення нотації Big O

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

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

Основні нотації:

O(1) — Константна складність:

• Час виконання алгоритму не залежить від розміру вхідних даних.
• Приклад: доступ до елементу масиву за індексом.

O(n) — Лінійна складність:

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

O(log n) — Логарифмічна складність:

• Час виконання алгоритму зростає логарифмічно з збільшенням розміру вхідних даних.
• Приклад: бінарний пошук у відсортованому масиві.

O(n^2) — Квадратична складність:

• Час виконання алгоритму квадратично залежить від розміру вхідних даних.
• Приклад: сортування бульбашкою, сортування вставками.

O(2^n) — Експоненціальна складність:

• Час виконання алгоритму експоненційно залежить від розміру вхідних даних.
• Приклад: розв'язання задачі про рюкзак повним перебором.

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

11.2 Інтерпретація нотації Big O

Як інтерпретувати і використовувати нотацію Big O?

Ігнорування констант і менш значущих членів: Big O описує порядок зростання функції, ігноруючи константи і менш значущі члени. Наприклад, O(2n) і O(3n) інтерпретуються як O(n).

Порівняння алгоритмів: Big O дозволяє порівнювати алгоритми за їх асимптотичною ефективністю. Наприклад, алгоритм з O(n log n) ефективніший, ніж алгоритм з O(n^2) для дуже великих обсягів даних.

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

Ігнорування констант

Розглянемо приклади ігнорування констант і менш значущих членів:

Приклад 1. Розглянемо дві функції:

• f(n) = 3n + 2
• g(n) = 5n + 1

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

Приклад 2. Розглянемо дві функції:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

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

11.3. Порівняння алгоритмів

1. Порівняння алгоритмів на дуже великих об'ємах даних

Приклад 1:

• Алгоритм A має часову складність O(n^2).
• Алгоритм B має часову складність O(n log n).

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

Приклад 2:

• Алгоритм X має часову складність O(n).
• Алгоритм Y має часову складність O(1).

Алгоритм Y буде завжди швидше, незалежно від розміру n, оскільки O(1) означає, що час виконання алгоритму не залежить від розміру вхідних даних.

2. Аналіз найгіршого випадку

Приклад 1:

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

Приклад 2:

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

3. Вплив на продуктивність та масштабованість

Приклад 1:

Якщо у нас є два алгоритми для обробки даних, один з часовою складністю O(n^2), а інший з O(n log n), і ми збільшуємо розмір даних з 1000 елементів до 10 000 елементів, різниця в продуктивності буде значно помітна.

• Алгоритм з O(n^2) буде виконувати приблизно 100 000 000 операцій для 10 000 елементів.
• Алгоритм з O(n log n) буде виконувати близько 40 000 операцій для 10 000 елементів.

Приклад 2:

Розглянемо алгоритм, який працює за O(2^n). Якщо ми збільшуємо розмір вхідних даних з 10 до 20 елементів, кількість операцій зростає експоненційно.

• Для n = 10: 2^10 = 1024 операцій.
• Для n = 20: 2^20 = 1 048 576 операцій.

Це показує, як швидко експоненціальна складність стає непрактичною для великих значень n.

1

Опитування

Структури даних, рівень 15, лекція 10

Недоступний

Структури даних

Структури даних

Відкрити