Оцінка складності алгоритмів, або Що таке О (log n)


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

Напевно ви не раз стикалися з позначеннями на кшталт O (log n) або чули фрази типу «логарифмічна обчислювальна складність» на адресу будь-яких алгоритмів. І якщо ви так і не розумієте, що це означає, – ця стаття саме для вас.

Оцінка складності

Складність алгоритмів зазвичай оцінюють за часом виконання або по використовуванні пам’яті. В обох випадках складність залежить від розмірів вхідних даних: масив з 100 елементів буде оброблений швидше, ніж аналогічний з 1000. При цьому точний час мало кого цікавить: воно залежить від процесора, типу даних, мови програмування і інших параметрів. Важлива лише асимптотична складність, тобто складність при прагненні розміру вхідних даних до нескінченності.

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

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

Приклади
O (n) – лінійна складність
Такою складністю володіє, наприклад, алгоритм пошуку найбільшого елемента в не відсортованому масиві. Нам доведеться пройтися по всіх n елементів масиву, щоб зрозуміти, який з них максимальний.

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

O (n2) – квадратична складність
Таку складність має, наприклад, алгоритм сортування вставками. У канонічній реалізації він вдає із себе два вкладених цикла: один, щоб проходити по всьому масиву, а другий, щоб знаходити місце чергового елементу в уже відсортованій частині. Таким чином, кількість операцій буде залежати від розміру масиву як n * n, тобто n2.
Бувають і інші оцінки за складністю, але всі вони засновані на тому ж принципі.

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

Аналогічно проводять оцінку і по пам’яті, коли це важливо. Однак алгоритми можуть використовувати значно більше пам’яті при збільшенні розміру вхідних даних, ніж інші, але працюватимуть швидше. І навпаки. Це допомагає вибирати оптимальні шляхи вирішення завдань виходячи з поточних умов і вимог.

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

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

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Trends: оцінка складності алгоритму

Коментарі 1

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

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *