Поняття складності алгоритмів 9 клас

. Теоретична частина

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

Види складності:

📌 Часова складність – скільки операцій виконується залежно від розміру вхідних даних (n).
📌 Просторова складність – скільки пам’яті споживає алгоритм.

Нотація "О" (О-нотація, Big-O Notation)

Оцінює, як швидко збільшується кількість операцій при зростанні n.

🔹 O(1) – алгоритм працює за сталий час (наприклад, доступ до елемента списку).
🔹 O(log n) – логарифмічний ріст (наприклад, бінарний пошук).
🔹 O(n) – лінійна складність (наприклад, простий перебір списку).
🔹 O(n²) – квадратична складність (наприклад, подвійний цикл).
🔹 O(2ⁿ) – експоненційна складність (дуже повільний алгоритм).

. Практична частина

Завдання 1: Вимірюємо час виконання алгоритмів

📌 Перевіримо, як змінюється час виконання алгоритму залежно від розміру даних.

🔎 Аналізуємо результат:
✅ Якщо список містить 10 елементів – швидко.
✅ Якщо список містить 1 000 000 елементів – значно довше.
✅ Це показує, що алгоритм O(n) працює повільніше на великих наборах даних.

Завдання 2: Порівнюємо два алгоритми сортування

📌 Порівняємо "бульбашкове сортування" (O(n²)) і вбудовану функцію Python (O(n log n)).
Пояснення роботи коду:

1️⃣ Генеруємо список із 500 випадкових чисел.
2️⃣ Сортуємо його двома різними способами:

• Бульбашковим сортуванням (повільний метод O(n²))

• Вбудованим методом Python (ефективний O(n log n))
  3️⃣ Порівнюємо час виконання обох алгоритмів.

💡 Очікуваний результат:
🔹 Бульбашкове сортування набагато повільніше, особливо якщо збільшити розмір списку.
🔹 Сортування Python працює швидко навіть для великих масивів.

Завдання 3: Оптимізація алгоритму пошуку

📌 Використаємо бінарний пошук (O(log n)), який значно швидший за лінійний (O(n)).

Завдання 3: Порівняння лінійного та бінарного пошуку

📌 Мета:

• Перевірити, який пошук працює швидше: лінійний (O(n)) чи бінарний (O(log n)).

• Зрозуміти, що бінарний пошук можна застосовувати лише на відсортованих масивах.

  Пояснення роботи коду:

  1️⃣ Лінійний пошук (O(n)) проходить кожен елемент списку поки не знайде потрібний.
  2️⃣ Бінарний пошук (O(log n)) працює набагато швидше:

  • Ділить список навпіл і перевіряє середній елемент.

  • Якщо число більше – шукає в правій половині.

  • Якщо число менше – шукає в лівій половині.
    3️⃣ Результати показують, що бінарний пошук в сотні разів швидший за лінійний!

Очікуваний результат:

⏳ Лінійний пошук (O(n)) – значно довший, особливо на великих масивах.
⚡ Бінарний пошук (O(log n)) – миттєвий результат, навіть при 1 000 000 елементах.

Домашнє завдання

1️⃣ Модифікуйте програму:

• Додайте новий алгоритм сортування (наприклад, "вставками").
  2️⃣ Напишіть власний алгоритм з O(1) (наприклад, отримання елемента за індексом).

🚀 Чим краще алгоритм – тим швидше працює програма! Вчимося вибирати ефективні рішення! 😉