Складність алгоритмів

Вітання! Сьогоднішня лекція трохи відрізнятиметься від інших. Відрізнятися вона буде тим, що має непряме відношення до Java. Тим не менш, ця тема є дуже важливою для кожного програміста. Ми поговоримо про алгоритми . Що таке алгоритм? Говорячи простою мовою, це деяка послідовність дій, які необхідно зробити для досягнення потрібного результату . Ми часто використовуємо алгоритми у повсякденному житті. Наприклад, щоранку перед тобою стоїть завдання: прийти на навчання чи роботу, і бути при цьому:

• Одягненим
• Чистим
• Ситим

Який алгоритм дозволить тобі досягти цього результату?

1. Прокинутися будильником.
2. Прийняти душ, вмитися.
3. Приготувати сніданок, зварити каву/заварити чай.
4. Поїсти.
5. Якщо не погладив одяг із вечора — погладити.
6. Одягтися.
7. Вийти з будинку.

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

1. Купити або завантажити в Інтернеті "Словник російських особистих імен" 1966 видання.
2. Знаходити кожне ім'я з нашого списку у цьому словнику.
3. Записувати на папірець, на якій сторінці словника є ім'я.
4. Розставити імена по порядку, використовуючи записи на папірці.

Чи дозволить така послідовність дій вирішити наше завдання? Так, цілком дозволить. Чи буде це рішення ефективним ? Навряд чи. Тут ми підійшли до ще однієї дуже важливої ​​властивості алгоритмів — їхньої ефективності . Розв'язати завдання можна у різний спосіб. Але і в програмуванні, і в звичайному житті ми вибираємо спосіб, який буде найефективнішим. Якщо твоє завдання зробити бутерброд з вершковим маслом, ти, звичайно, можеш почати з того, що посієш пшеницю і подоїш корову. Але це буде неефективнерішення - воно займе дуже багато часу і коштуватиме багато грошей. Для вирішення твого простого завдання хліб і масло можна просто купити. А алгоритм із пшеницею та коровою хоч і дозволяє вирішити завдання, надто складне, щоб застосовувати його на практиці. Для оцінки складності алгоритмів у програмуванні створабо спеціальне позначення під назвою Big-O (“велика”) . Big-O дозволяє оцінити, наскільки час виконання алгоритму залежить від переданих до нього даних. Давай розглянемо найпростіший приклад – передачу даних. Уяви, що тобі потрібно передати деяку інформацію у вигляді файлу на велику відстань (наприклад, 5000 км). Який алгоритм буде найефективнішим? Це залежить від тих даних, з якими він має працювати. Наприклад, ми маємо аудіофайл розміром 10 мегабайт. У цьому випадку найефективнішим алгоритмом буде передати файл через Інтернет. Це займе максимум кілька хвабон! Отже, ще раз озвучимо наш алгоритм: “Якщо потрібно передати інформацію у вигляді файлів на відстань 5000 кілометрів, потрібно використовувати передачу даних через Інтернет”. Чудово. Тепер проаналізуємо його. Чи вирішує він наше завдання?Загалом так, цілком вирішує. А ось що можна сказати щодо його складності? Хм, а ось тут уже все цікавіше. Справа в тому, що наш алгоритм дуже залежить від вхідних даних, а саме — від розміру файлів. Зараз у нас 10 мегабайт, і все гаразд. А якщо нам потрібно буде передати 500 мегабайт? 20 гігабайт? 500 терабайт? 30 петабайт? Чи перестане наш алгоритм працювати? Ні, всі ці обсяги даних все одно можна передати. Чи стане він виконуватися довше? Так, стане! Тепер нам відома важлива особливість нашого алгоритму: чим більший розмір даних для передачі, тим довше займе виконання алгоритму. Але нам хотілося б більш точно розуміти, як виглядає ця залежність (між розміром даних та часом на їх передачу). У нашому випадку складність алгоритму буде лінійною . "Лінійна" означає, що при збільшенні обсягу даних час на їх передачу зросте приблизно пропорційно. Якщо даних стане вдвічі більше, і часу на їх передачу знадобиться вдвічі більше. Якщо даних побільшає в 10 разів, і час передачі збільшиться в 10 разів. Використовуючи позначення Big-O, складність нашого алгоритму визначається як O(N). Це позначення найкраще запам'ятати на майбутнє – воно завжди використовується для алгоритмів із лінійною складністю. Зверни увагу: ми взагалі не говоримо тут про різні “змінні” речі: швидкість інтернету, потужність нашого комп'ютера тощо. При оцінці складності алгоритму в цьому немає сенсу — ми в жодному разі не можемо це контролювати. Big-O оцінює саме сам алгоритм, незалежно від “довкілля” у якому йому доведеться працювати. Продовжимо працювати з нашим прикладом. Припустимо, у результаті з'ясувалося, що обсяг файлів передачі становить 800 терабайт. Якщо ми передаватимемо їх через Інтернет, завдання, звичайно, буде вирішено. Є тільки одна проблема: передача стандартним сучасним каналом (зі швидкістю 100 мегабіт в секунду), який використовується вдома у більшості з нас, займе приблизно 708 днів. Майже 2 роки! :O Так, наш алгоритм тут явно не підходить. Потрібне якесь інше рішення! Несподівано на допомогу до нас приходить IT-гігант – компанія Amazon! Її сервіс Amazon Snowmobile дозволяє завантажити великий обсяг даних у пересувні сховища та доставити за потрібною адресаою на вантажівці! Отже, ми маємо новий алгоритм! Якщо потрібно передати інформацію у вигляді файлів на відстань 5000 кілометрів і цей процес займе більше 14 днів при передачі через Інтернет, потрібно використовувати перевезення даних на вантажівці Amazon. Цифра 14 днів тут обрана випадково: припустимо, це максимальний термін, який ми можемо собі дозволити. Давай проаналізуємо наш алгоритм. Що щодо швидкості? Навіть якщо вантажівка поїде зі швидкістю всього 50 км/год, вона подолає 5000 кілометрів всього за 100 годин. Це трохи більше чотирьох днів! Це набагато краще, ніж варіант із передачею по інтернету. А що зі складністю цього алгоритму? Чи буде вона також лінійною, O(N)? Ні не буде. Адже вантажівці не має значення, як сильно ти її навантажиш — вона все одно поїде приблизно з тією ж швидкістю і приїде вчасно. Чи буде у нас 800 терабайт, чи в 10 разів більше даних, вантажівка все одно доїде до місця за 5 днів. Іншими словами, алгоритм доставки даних через вантажівку має постійну складність.. "Постійна" означає, що вона не залежить від даних, що передаються в алгоритм. Поклади у вантажівку флешку на 1Гб - він доїде за 5 днів. Поклади туди диски з 800 терабайт даних - він доїде за 5 днів. При використанні Big-O постійна складність позначається як O(1) . Якщо ми познайомабося з O(N) і O(1) , давай тепер розглянемо більш "програмістські" приклади :) Припустимо, тобі дано масив зі 100 чисел, і завдання - вивести в консоль кожне з них. Ти пишеш звичайний цикл for, який виконує це завдання

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

Яка складність написаного алгоритму? Лінійна, O(N). Число дій, які має зробити програма, залежить від того, скільки саме чисел у неї передали. Якщо в масиві буде 100 чисел, дій (висновків на екран) буде 100. Якщо чисел у масиві буде 10000, потрібно буде здійснити 10000 дій. Чи можна покращити наш алгоритм? Ні. Нам у будь-якому випадку доведеться здійснити N проходів масивом і виконати N висновків в консоль. Розглянемо інший приклад.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

У нас є порожній LinkedList, в який ми вставляємо кілька чисел. Нам потрібно оцінити складність алгоритму вставки одного числа у LinkedListнашому прикладі, і як вона залежить від числа елементів, що знаходяться в списку. Відповіддю буде O(1) — постійна складність . Чому? Зверніть увагу: щоразу ми вставляємо число на початок списку. До того ж, як ти пам'ятаєш, при вставці числа в LinkedListелементи нікуди не зрушуються - відбувається перевизначення посилань (якщо раптом забув, як працює LinkedList, зазирни в одну з наших старих лекцій ). Якщо зараз перше число в нашому списку - число х, а ми вставляємо на початок списку число y, все, що для цього потрібно:

x.previous  = y;
y.previous = null;
y.next = x;

Для цього перевизначення посилань нам неважливо, скільки чисел зараз уLinkedList хоч одне, хоч мільярд. Складність алгоритму буде постійною – O(1).

Логарифмічна складність

Без паніки! :) Якщо при слові "логарифмічний" тобі захотілося закрити лекцію і не читати далі - почекай пару хвабон. Жодних математичних складнощів тут не буде (таких пояснень повно і в інших місцях), а всі приклади розберемо "на пальцях". Уяви, що твоє завдання знайти одне конкретне число в масиві зі 100 чисел. Точніше, перевірити, чи воно там взагалі. Як тільки потрібне число знайдено, пошук припинити, а в консоль вивести запис “Потрібне число виявлено! Його індекс у масиві = ....” Як би ти вирішив таке завдання? Тут рішення очевидне: потрібно перебрати елементи масиву по черзі починаючи з першого (або з останнього) і перевіряти, чи поточне число збігається з шуканим. Відповідно, кількість дій прямо залежить від кількості елементів у масиві. Якщо у нас 100 чисел, значить, нам потрібно 100 разів перейти до наступного елементу та 100 разів перевірити число на збіг. Якщо чисел буде 1000, то й кроків-перевірок буде 1000. Це очевидно лінійна складність,O(N) . А тепер ми додамо до нашого прикладу одне уточнення: масив, в якому тобі потрібно знайти число, відсортований за зростанням . Чи змінює це щось для нашого завдання? Ми, як і раніше, можемо шукати потрібну кількість перебором. Але натомість ми можемо використовувати відомий алгоритм двійкового пошуку . У верхньому ряду на зображенні бачимо відсортований масив. У ньому нам необхідно знайти число 23. Замість того щоб перебирати числа, ми просто ділимо масив на 2 частини і перевіряємо середнє число в масиві. Знаходимо число, яке розташовується в комірці 4 і перевіряємо його (другий рядок на картинці). Це число рівне 16, а ми шукаємо 23. Поточне число менше. Що це означає? Що всі попередні числа (які розташовані до числа 16) можна не перевіряти: вони точно будуть меншими за те, яке ми шукаємо, адже наш масив відсортований! Продовжимо пошук серед 5 елементів, що залишабося. Зверни увагу:ми зробабо лише одну перевірку, але вже міли половину можливих варіантів. У нас залишилося лише 5 елементів. Ми повторимо наш крок - знову розділимо масив, що залишився на 2 і знову візьмемо середній елемент (рядок 3 на малюнку). Це число 56, і воно більше за те, яке ми шукаємо. Що це означає? Що ми відкидаємо ще три варіанти - саме число 56, і два числа після нього (вони точно більше 23, адже масив відсортований). У нас залишилося всього 2 числа для перевірки (останній ряд на малюнку) — числа з індексами масиву 5 та 6. Перевіряємо перше з них, і це те, що ми шукали, — число 23! Його індекс = 5! Давайте розглянемо результати роботи нашого алгоритму, а потім розберемося з його складністю. (До речі, тепер ти розумієш, чому його називають двійковим: його суть полягає у постійному розподілі даних на 2). Результат вражає! Якби ми шукали потрібну кількість лінійним пошуком, нам знадобилося б 10 перевірок, а з двійковим пошуком ми вклалися у 3! У гіршому випадку їх було б 4, якби на останньому кроці необхідним числом виявилося друге, а не перше. А що з його складністю? Це дуже цікавий момент:) Алгоритм двійкового пошуку набагато менше залежить від кількості елементів у масиві, ніж алгоритм лінійного пошуку (тобто простого перебору). При 10 елементах у масиві лінійному пошуку знадобиться максимум 10 перевірок, а двійковому – максимум 4 перевірки. Різниця у 2,5 рази. Але для масиву в 1000 елементів лінійному пошуку знадобиться 1000 перевірок, а двійковому – всього 10 ! Різниця вже у 100 разів! Зверни увагу:кількість елементів у масиві збільшилася в 100 разів (з 10 до 1000), а кількість необхідних перевірок для двійкового пошуку збільшилася всього в 2,5 рази — з 4 до 10. Якщо ми дійдемо до 10000 елементів, різниця буде ще більш вражаючою: 10000 перевірок для лінійного пошуку, і лише 14 перевірок для двійкового. І знову: кількість елементів збільшилася в 1000 разів (з 10 до 10000), а кількість перевірок збільшилася лише у 3,5 рази (з 4 до 14). Складність алгоритму двійкового пошуку логарифмічна , або, якщо використовувати позначення Big-O, - O (log n). Чому вона так називається? Логарифм - це така штуковина, обернена до зведення в ступінь. Двійковий логарифм використовує для підрахунку ступеня числа 2. Ось, наприклад, ми маємо 10000 елементів, які нам треба перебрати двійковим пошуком. Зараз у тебе є картинка перед очима, і ти знаєш, що для цього потрібно максимум 14 перевірок. Але якщо картинки перед очима не буде, а тобі потрібно порахувати точну кількість необхідних перевірок? Досить відповісти на просте запитання: в який ступінь треба звести число 2, щоб отриманий результат був числу елементів, що перевіряються? Для 10000 це буде 14 ступінь. 2 в 13 ступені - це занадто мало (8192) А ось 2 в 14 ступені = 16384, це число задовольняє нашій умові (воно >= числу елементів у масиві). Ми знайшли логарифм — 14. Стільки перевірок нам потрібно! :) Алгоритми та їх складність - тема занадто велика, щоб вмістити її в одну лекцію. Але знати її дуже важливо: на багатьох співбесідах ти матимеш алгоритмічні завдання. Для теорії я можу порадити тобі кілька книжок. Почати можна з “ Грокуємо алгоритми ”: хоча приклади в книзі написані на Python, мова книги та приклади дуже прості. Найкращий варіант для новачка, до того ж вона невелика за обсягом. З серйознішого читання — книги Роберта Лафоре і Роберта Седжвіка. Обидві написані на Java, що зробить вивчення для тебе трохи простіше. Адже ти непогано знайомий із цією мовою! :) Для учнів з гарною математичною підготовкою найкращим варіантом буде книга Томаса Кормена . Але однією теорією ситий не будеш! "Знати" != "вміти" Практикувати рішення задач на алгоритми можна на HackerRank та Leetcode . Завдання звідти часто використовують навіть на співбесідах в Google і Facebook, так що нудно тобі точно не буде :) Для закріплення матеріалу лекції, раджу подивитися чудове відео про Big-O на YouTube. Побачимося на наступних лекціях! :)