Для оцінки ефективності програми в JavaScript, як і в багатьох інших мовах програмування, використовують складність алгоритмів.
Це ті два слова, яких бояться так багато починаючих розробників (а може не тільки починаючих)😉
Тож сьогодні я спробую якомога простіше і доступніше пояснити, що О(n) - це не настільки страшно, як ви думали. Поїхали.
Почнемо з того, що таке алгоритм як окрема одиниця.
Алгоритм — це чітка послідовність команд для досягнення певної мети.
Алгоритми є фундаментальним елементом програмування.
Зазвичай (і це чи не єдино правильний варіант) алгоритми використовують для вирішення складних задач шляхом послідовного виконання простих команд.
У алгоритмів є характеристики, без урахування яких неможливо написати правильний алгоритм. Список основних характеристик:
- Мета алгоритму:
це визначальна властивість алгоритму. Простіше - де ми можемо цей алгоритм застосувати. Наприклад, ми можемо або стискати якісь дані, або перебирати масив.
- Точність алгоритму:
це відповідь на питання “чи вірогідність правильного виконання цього алгоритму дорівнює 1?”
- Швидкість алгоритму:
тут все дуже просто. Це час, за який алгоритм встигає повністю виконатися і ще можливу зміну часу виконання, в залежності від кількості вхідних параметрів.
- Методи побудови алгоритму:
якщо ви пишете власний алгоритм, то вам точно треба знати найпопулярніші методи побудови алгоритмів. Ви можете взяти за основу, наприклад, метод випадкового пошуку, чи метод декомпозиції, або ж метод послідовних наближень.
- і нарешті його величність - Складність алгоритму:
найчастіше використовувана та одна із найважливіших характеристик.
Складність алгоритму включає в себе кількість задіяної памʼяті при виконанні алгоритму, та витрачений на це час.
Для того, щоб правильно використовувати алгоритми, потрібно вміти правильно вираховувати їх складність.
Що ж таке O від n?
Літерою n прийнято позначати кількість вхідних даних. О - це скорочення від математичного терміну “О-нотація”. Фактично О - це функція, яка визначає, як змінюватиметься обчислювальна складність алгоритму при зміні кількості вхідних даних.
Давайте поясню на прикладі. Якщо ми говоримо про сортування, наприклад, то під час роботи з різними структурами даних нам дуже важливо підібрати правильний алгоритм сортування. Остаточний вибір між різними варіантами залежить від кількості вхідних даних і бажаної ефективності самого сортування.
Візьмемо один із найпопулярніших, той, який у всіх “на слуху” - алгоритм бульбашкового сортування. В ньому при кожному проходженні масивом елементи будуть порівнюватися парами і, зазвичай, той, що менший - буде зліва. Тобто у вхідній послідовності будуть порівнюватися два сусідні елемента, і , якщо вони не будуть відповідати критерію сортування, то будуть мінятися місцями. Це буде продовжуватися до тих пір, поки весь масив елементів не буде відсортовано.
Задача в тому, що нам зараз потрібно порахувати складність цього алгоритму.
Вхідний масив має, до прикладу, 10 елементів і виходить, що n = 10.
Уявімо, що вхідний масив відсортований в зворотному порядку, тобто від 10 до 1.
У такому випадку алгоритму доведеться 10 разів пройтися по масиву, кожен раз міняючи сусідні елементи місцями, а це означає, що для цього потрібно виконати аж цілих 100 команд, де одна команда - це спочатку порівняння , а потім перестановка.
Підготував для вас таблицю, яка має полегшити розуміння, адже всі ми краще розуміємо, коли бачимо наглядний приклад, так?
За таких умов 100 команд - це n², тобто ми можемо оцінити складність цього алгоритму як O(n²). Вуаля, ми навчилися це робити!
Сама складність алгоритмів теж, само собою, має деяку глибину, що додає їй декілька цікавих аспектів:
- Асимптотична нотація
Асимптотична нотація - це спосіб оцінки складності алгоритму для великого обсягу даних, також це називають Big O. Використовується для просторової та часової оцінки складності для розуміння як зростає час виконання і зростання кількості використаної памʼяті відповідно до зростаючої кількості вхідних даних.
- Найгірший, середній та кращий випадоки
Складність алгоритму може бути оцінена в залежності від того, як він поводить себе в залежності від різних вхідних даних. Найгірший випадок описує найбільшу кількість операцій, середній - середню кількість, а кращий - найменшу. Це важливо для розуміння того, як алгоритм працює у різних умовах.
- Складність пам'яті
Це оцінка не лише часової, а й просторової складності алгоритму. Іноді може бути доцільно вибирати менш ефективний з точки зору часової складності алгоритм на користь меншого використання пам'яті або навпаки. Це може зекономити немало бюджету для компанії.3
- Принципи оптимізації
Іноді можна змінити або оптимізувати алгоритм для зниження його складності. Це може включати використання кращих структур даних, уникнення зайвих операцій або використання інших алгоритмічних підходів.
- Підтримка розширюваності
Деякі алгоритми можуть бути більш складними, але забезпечувати кращу розширюваність програми. Вибір алгоритму може також залежати від потреб майбутнього розвитку проекту.
Висновок
Розуміння складності алгоритмів - це буквально критично важлива штука для успішного розвитку програмного забезпечення у будь-якій мові програмування, і JavaScript точно не є виключенням із правил.
Надзвичайно важливо мати чітке уявлення про те, як часова та просторова складності алгоритмів впливають на продуктивність програми. Оцінка алгоритмів допомагає розробникам створювати швидке, ефективне та масштабоване програмне забезпечення.
Проте це лише одна з глибоких тем програмування. Серед спеціалістів дуже цінуються люди, які хочуть та досліджують ще більше аспектів програмування, таких як архітектура програм, патерни проектування, робота з базами даних та інші. Про це все я з величезною радістю поділюся в наступних статтях!
Поглиблене вивчення цих тем дозволить вам стати більш компетентним розробником і зробить ваші проекти ще більш успішними та стійкими до більшості проблем, які виникають за незнанням :)
