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


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

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

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


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

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

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

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

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

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

Порядок зростання описує те, як складність алгоритму росте зі збільшенням розміру вхідних даних. Найчастіше він представлений у вигляді 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”

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

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