Що таке складність алгоритму?
Уяви, що тобі треба знайти певний вірш у збірці Тараса Шевченка «Кобзар». Те, як швидко ти його знайдеш, залежить не лише від твоєї швидкості, а й від того, який метод (алгоритм) ти обереш.
Складність алгоритму — це міра того, скільки ресурсів (часу або пам'яті) витрачає комп'ютер на виконання програми залежно від обсягу вхідних даних (кількості слів, чисел тощо).
Зазвичай ми говоримо про часову складність:
-
Лінійна складність: Ти перевіряєш кожну сторінку по черзі з першої до останньої. Якщо в книжці 100 сторінок — ти зробиш до 100 кроків. Якщо 1000 — до 1000 кроків.
-
Стала складність: Ти точно знаєш номер сторінки й одразу відкриваєш її. Незалежно від того, наскільки товста книга, ти робиш лише 1 дію.
📝 Практичне завдання «Пошук „Заповіту“»
Контекст:
У нас є список назв творів Тараса Шевченка, відсортований за алфавітом. Нам потрібно знайти, чи є у списку твір «Заповіт».
Твій список:
-
Гайдамаки
-
Гамалія
-
Заповіт
-
Катерина
-
Наймичка
Завдання:
-
Порахуй, скільки кроків (порівнянь) зробить алгоритм, який перевіряє кожну назву по черзі (лінійний пошук), щоб знайти «Заповіт».
-
Уяви, що список виріс до 100 творів, і «Заповіт» опинився в самому кінці. Скільки кроків знадобиться тоді?
✅ Розв’язок завдання
-
Для короткого списку:
-
Крок 1: Це «Гайдамаки»? Ні.
-
Крок 2: Це «Гамалія»? Ні.
-
Крок 3: Це «Заповіт»? Так!
-
Відповідь: Алгоритм зробив 3 кроки.
-
Для списку зі 100 творів:
-
Якщо ми шукаємо «Заповіт» лінійним пошуком і він останній, нам доведеться порівняти його з усіма попередніми назвами.
-
Відповідь: Алгоритм зробить 100 кроків.
Висновок: Лінійна складність означає, що кількість роботи росте прямо пропорційно кількості даних. У програмуванні це позначають як O(n).
|