Найперше, розберемось з тим що таке складність алгоритму. Це спосіб оцінити, скільки ресурсів алгоритм споживає в залежності від розміру вхідних даних. Існує два способи, щоб виміряти складність алгоритму.
Time Complexity
Часова складність алгоритму - це спосіб зрозуміти, наскільки він повільнішає, коли даних стає більше. Для вимірювання використовується Big O нотація, яка показує верхню межу вимірювання.
Розберемо детальніше
O(1) - Яскравим прикладом константної складності є операція присвоювання, або доступ до поля обʼєкта по ключу.
O(log n) - При цій складності, час виконання росте дуже повільно, навіть при значному збільшенні вхідних даних. Прикладів його застосування дуже багато і найпростіший це бінарний пошук.
O(n) - При цій складності, час виконання росте прямо пропорційно збільшенню кількості елементів. Наприклад, ми перебираємо масив з 100 елементів. При використанні алгоритму з логарифмічною складність, при збільшенню кількості елементів до 100 000, ми майже не відчуємо змін в часі виконання алгоритму, тоді як при використанні O(n) алгоритм значно сповільниться.
O(n log n) - Простими словами це поєднання лінійної і логарифмічної складності. Наприклад наш алгоритм використовує стратегію divide and conquer O(log n), щоб розділяти масив і використовує перебір O(n), щоб обробити усі елементи.
O(n²) - Це відбувається тоді, коли для кожного елемента алгоритм перевіряє всі інші елементи. Найчастіше, коли є два вкладені цикли.
O(2ⁿ) - Експоненційна складність є найповільнішою серед всіх. Якщо описати її простими словами, то вона подвоює кількість операції. Наприклад, на 10 елементів, потрібно буде зробити орієнтовно 1024 операції.
Простий приклад визначення складності алгоритму
В нас є функція, яка повертає мінімальне значення масиву. Фактично ми маємо 2 операції, це присвоєння в let min = arr[0] i перебір масиву arr . Операція присвоєння завжди займає константний час O(1), так як не залежить від кількості елементів, тоді як при переборі масиву ми залежимо від кількості елементів в цьому масиві тому складність буде O(n). Визначення складності алгоритму, відбувається по найскладнішій операції. В нас це перебір масиву тому складність функції findMin буде O(n).
Space Complexity
Це кількість додаткової пам’яті, яку алгоритм потребує, окрім вхідних даних. Наприклад, створення додаткових змінних, масивів, обʼєктів і тд. Для визначення space complexity ми використовуємо ту саму Big O нотацію, але оперуємо не кількістю операцій, а кількістю задіяних структур.
Після того як ви відповіли на питання, буде дуже великим плюсом наголосити на важливість розуміння складності, так як це має пряме відношення до розуміння структур даних, а стркутури є фундаментом для розуміння сучасних розподілених систем, баз даних, кешування і багатьох інших важливих тем.