Часова складність у програмуванні визначає, як швидко зростає кількість операцій (час виконання) алгоритму при збільшенні розміру вхідних даних. Давайте розглянемо це на прикладі магічних заклинань:
1. Константна складність (O(1)): якщо ви маєте заклинання, яке завжди виконується за один крок, то це константна складність. Наприклад:
- Викликати заклинання "Відкрити двері" (незалежно від типу дверей).
Переваги:
-Швидкий доступ до результату незалежно від розміру вхідних даних.
-Простота реалізації.
Недоліки:
-Не підходить для завдань, де потрібно обробляти багато даних.
2. Лінійна складність (O(n)): якщо кількість операцій зростає пропорційно з розміром вхідних даних, то це лінійна складність. Наприклад:
- Перевірити, чи є певний заклинаний артефакт у списку артефактів.
Цей тип працює добре для невеликих наборів даних, але при збільшенні розміру вхідних даних час виконання зростає лінійно, себто пропорційно. Іншими словами, якщо ми подвоїмо розмір вхідних даних, то час виконання також збільшиться приблизно вдвічі.
3. Логарифмічна складність (O(log n)): якщо ви ділите вхідні дані на половини і виконуєте операції залежно від результату, то це логарифмічна складність. Наприклад:
- Знайти заклинання в відсортованому списку заклинань за назвою.
Перевагою є те, що ми отримуємо швидкий доступ до даних навіть для великих наборів та ідеально підходить для пошуку відсортованих даних. Але цей тип досить складно реалізувати.
Притаманно для quick sort та merge sort.
4. Квадратична складність (O(n^2)): якщо ви виконуєте операції для кожної пари елементів вхідних даних, то це квадратична складність. Наприклад:
- Порівняти всі пари заклинань між собою.
Цей же реалізувати простіше, але добре працює для невеликих наборів даних. Час виконання зростає квадратично при збільшенні розміру даних, а це значить, що якщо ми подвоїмо розмір вхідних даних, то час виконання збілбшиться приблизно вчетверо.
Притаманно для bubble sort та insertion sort.
5. Експоненціальна складність (O(2^n)): якщо кількість операцій зростає експоненційно з розміром вхідних даних, то це експоненціальна складність. Наприклад:
- Знайти всі можливі комбінації заклинань.
Використовується для вирішення задач з обмеженим розміром вхідних даних, але непридатний для великих наборів через експоненційне(тобто дуже швидке) зростання часу виконання, тому такі алгоритми часто потребують оптимізації або заміни більш ефективними альтернативами.