Алгоритми і структури даних для початківців: складність алгоритмів


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

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

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

Розуміння алгоритмів і структур даних розпочинається з уміння визначати і порівнювати їх складність.


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

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

Асимптотичний аналіз

Коли ми говоримо про вимір складності алгоритмів, то маємо на увазі аналіз часу, який знадобиться для обробки дуже великого набору даних. Такий аналіз називають “асимптотичним”. Скільки часу знадобиться на обробку масиву з десяти елементів? Тисячі? Десяти мільйонів? Якщо алгоритм обробляє тисячу елементів за п’ять мілісекунд, що станеться, якщо ми передамо в нього мільйон? Чи буде він виконуватися п’ять хвилин або п’ять років? Чи не варто з’ясувати це раніше замовника?

Усе вирішують дрібниці!

Порядок зростання

Порядок зростання описує те, як складність алгоритму росте зі збільшенням розміру вхідних даних. Найчастіше він представлений у вигляді O-нотації (від нім. “Ordnung” – порядок): O (f (x)), де f (x) – формула, що виражає складність алгоритму. У формулі може бути присутньою змінна n, що представляє розмір вхідних даних. Нижче наводиться список порядків зростання, що найчастіше зустрічаються, але він у жодному разі не повний.

Константний – O(1)

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

public int GetCount (int[] items){
return items.Length;}

Лінійний – O(n)

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

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

public long GetSum (int[] items){ long sum = 0; foreach (int i in items) { sum += i; } return sum;}

Логарифмічний – O(log n)

Порядок зростання O (log n) означає, що час виконання алгоритму росте логарифмічно зі збільшенням розміру вхідного масиву. (Прим. перекл.: в аналізі алгоритмів за умовчанням використовується логарифм з основою 2). Більшість алгоритмів, які працюють за принципом “ділення навпіл”, мають логарифмічну складність. Метод Contains бінарного дерева пошуку (binary search tree) має порядок зростання O(log n).

Лінеарифметичний – O(n·log n)

Лінеарифметичний (чи лінійно-логарифмічний) алгоритм має порядок зростання O(n·log n). Деякі алгоритми типу “розділяй і володарюй” потрапляють до цієї категорії. У наступних частинах ми побачимо два таких приклади – сортування злиттям і швидке сортування.

Квадратичний – O(n 2)

Час роботи алгоритму з порядком зростання O(n 2) залежить від квадрата розміру вхідного масиву. Попри те, що такої ситуації іноді не уникнути, квадратична складність – привід переглянути використовувані алгоритми або структури даних. Проблема полягає в тому, що вони погано масштабуються. Наприклад, якщо масив з тисячі елементів потребує 1 000 000 операцій, масив з мільйона елементів – 1 000 000 000 000 операцій. Якщо одна операція вимагає мілісекунду для виконання, квадратичний алгоритм оброблятиме мільйон елементів 32 роки. Навіть якщо він буде в сто разів швидше, робота триватиме 84 дні.

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

Найкращий, середній і найгірший випадки

Що ми маємо на увазі, коли говоримо, що порядок зростання складності алгоритму – O (n) ? Це усереднений випадок? Чи найгірший? А може бути, найкращий?

Зазвичай мається на увазі найгірший випадок, за винятком тих випадків, коли найгірший і середній сильно різняться. Як-от: ми бачимо приклади алгоритмів, які в середньому мають порядок зростання O(1), але періодично можуть ставати O(n) (наприклад, ArrayList.add). У цьому випадку ми вказуватимемо, що алгоритм працює в середньому за константний час, і доведеться пояснювати випадки, коли складність зростає.

Найважливіше тут те, що O(n) означає: алгоритм потребує не більше n кроків.

Що ми вимірюємо?

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

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

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

Операції, кількість яких ми вимірюватимемо, включають:

  • порівняння (“більше”, ” менше”, ” дорівнює”);
  • привласнення;
  • виділення пам’яті.

Те, які операції ми враховуємо, зазвичай ясно з контексту.

Наприклад, при описі алгоритму пошуку елемента в структурі даних ми майже напевно маємо на увазі операції порівняння. Пошук – це переважно процес читання, так що немає сенсу робити привласнення або виділення пам’яті.

Коли ми говоримо про сортування, то можемо враховувати як порівняння, так і виділення і привласнення. У таких випадках ми явно вказуватимемо, які операції ми розглядаємо.

Продовження триває

На цьому ми закінчуємо знайомство з аналізом складності алгоритмів. Наступного разу ми розглянемо першу структуру даних – зв’язний список.

Переклад статті “Algorithms and Data Structures”

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


Trends: динамічний масив python, алгоритми і структури даних js, алгоритмічні структури пайтона

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

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