Вступ до часової складності алгоритмів

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

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

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

Складність часу

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

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

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

1. Лінійний пошук.

2. Бінарний пошук.

Скажімо, масив містить десять елементів, і ми маємо знайти число десять у масиві.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

Алгоритм лінійного пошуку порівнює кожен елемент масиву з цифрою пошуку . Коли він знаходить цифру_значення в масиві, він повертає true .

Тепер підрахуємо кількість операцій, які він виконує. Тут відповідь 10 (оскільки він порівнює кожен елемент масиву). Отже, Лінійний пошук використовує десять операцій для пошуку даного елемента (це максимальна кількість операцій для цього масиву; у випадку Лінійного пошуку це також відомо як найгірший випадок алгоритму).

Загалом, для лінійного пошуку в найгіршому випадку буде потрібно n операцій (де n - розмір масиву).

Давайте розглянемо алгоритм двійкового пошуку для цього випадку.

Бінарний пошук можна легко зрозуміти на цьому прикладі:

Джерело: Learneroo

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

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

кількість операцій = журнал (10) = 4 (приблизно)

для основи 2

Ми можемо узагальнити цей результат для двійкового пошуку як:

Для масиву розміром n кількість операцій, виконуваних двійковим пошуком, становить: log (n)

Позначення Великого О

У наведених вище твердженнях ми побачили, що для масиву розміром n лінійний пошук виконуватиме n операцій для завершення пошуку. З іншого боку, двійковий пошук виконував журнал (n) кількість операцій (як для найгірших випадків). Ми можемо представити це як графік ( вісь х : кількість елементів, вісь у : кількість операцій).

Джерело: Techtud

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

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

Наприклад, складність часу для лінійного пошуку може бути представлена ​​як O (n) та O (log n) для двійкового пошуку (де n та log (n) - це кількість операцій).

Складність часу або великі позначення O для деяких популярних алгоритмів перелічені нижче:

  1. Двійковий пошук: O (log n)
  2. Лінійний пошук: O (n)
  3. Швидке сортування: O (n * log n)
  4. Сортування вибору: O (n * n)
  5. Подорожній продавець: O (n!)

Висновок

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

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

Наприклад, якщо у нас є 4 мільярди елементів для пошуку, то, в гіршому випадку, для виконання лінійного пошуку потрібно 4 мільярди операцій. Двійковий пошук виконає це завдання лише за 32 операції. Це велика різниця. Тепер припустимо, що якщо одна операція займає 1 мс для завершення, то двійковий пошук займе всього 32 мс, тоді як лінійний пошук займе 4 млрд мс (це приблизно 46 днів). Це суттєва різниця.

Це причина, чому вивчення складності часу стає важливим, коли йдеться про таку велику кількість даних.

Ресурси

Grokking Algorithms - від Aditya Y Bhargava

Вступ до нотацій Big O та складності часу - від CS Dojo