Урок 57-58. Поняття складності алгоритму

Перегляньте та законспектуйте презентацію

🚀 Чому це важливо для інженера?

Уявіть, що ви розробили ідеальний алгоритм для керування безпілотником. Але під час польоту з'ясовується, що обчислення займають 10 секунд, хоча рішення потрібно прийняти за 0.1 секунди. Чи можна взагалі отримати результат вчасно? Відповідь на це дає теорія алгоритмів — наука про те, як ефективно витрачати ресурси комп'ютера.

🔍 Анатомія складності

В інженерії «складність» — це не про те, наскільки важко зрозуміти код, а про те, скільки ресурсів він споживає.

📈 Оцінка складності: О-нотація (O-notation)

Інженери не міряють швидкість алгоритму в секундах (бо на потужному ПК він летить, а на старому смартфоні — гальмує). Ми міряємо швидкість зростання витрат при збільшенні вхідних даних (n).

💡 Важливо: Ми завжди оцінюємо найгірший сценарій. Якщо ми шукаємо деталь на складі, ми припускаємо, що вона лежить у самому останньому ящику.

🏗️ Каталог алгоритмічних швидкостей

1. Константна складність O(1) — «Миттєвий доступ»

Час виконання не залежить від того, скільки даних ми маємо.

• Приклад: Дізнатися номер будинку за адресою або взяти третій елемент з масиву. Вам не треба переглядати весь масив — ви просто берете те, що потрібно.

2. Лінійна складність O(n) — «Пряма залежність»

Якщо даних стало вдвічі більше, часу знадобиться теж вдвічі більше.

• Приклад: Пошук найважчої коробки серед n несортованих коробок. Треба підняти кожну.

• Кейс: Пошук одиниці в рядку з n символів. У найгіршому випадку ви перевірите всі символи до кінця.

3. Квадратична складність O(n2) — «Пастка для продуктивності»

Якщо даних стало вдвічі більше, час виконання зростає в чотири рази. Це зазвичай трапляється, коли один цикл вкладений в інший.

• • Приклад: Сортування бульбашкою або порівняння кожного елемента з кожним.

4. Кубічна складність O(n3) — «Критична зона»

Означає, що час роботи алгоритму зростає пропорційно кубу кількості вхідних даних (n). При збільшенні обсягу даних у 2 рази, час виконання зростає у 8 разів. Зазвичай це свідчить про наявність трьох вкладених циклів у коді, що обробляють набір даних. 

👩‍ Практикум: Рахуємо складність «на око»

Розглянемо фрагмент коду для обробки матриці A[n × n] (знаходження максимуму в кожному рядку):

for i:=1 to N do         // Зовнішній цикл: повторюється N разів
  begin
    max:=A[i,1];
      for j:=1 to N do       // Внутрішній цикл: на кожну ітерацію i виконується ще N разів
          if A[i,j] > max then max:=A[i,j];
    writeln(max);
  end;

Інженерний аналіз

Внутрішній цикл робить n операцій. Оскільки він запускається n разів зовнішнім циклом, загальна кількість операцій — n × n = n2.

Вердикт: Складність алгоритму — O(n2).

🏁 Підсумок: Кодекс розробника

Обираючи алгоритм, завжди ставте собі питання:

1. Що станеться з програмою, якщо кількість користувачів виросте з 100 до 1 000 000?

2. Чи можу я замінити вкладений цикл O(n2) на один прохід O(n)?

3. Чи варта ця точність обчислень витраченого часу?

Перегляньте і виконайте інтерактивні завдання

Практичне завдання

Увага! Під час роботи з комп'ютером дотримуйтеся правил безпеки та санітарно-гігієнічних норм.

Повторіть правила безпечної роботи за комп’ютером.

🏢 Кейс «Розумне місто» (Smart City Optimization)

Легенда: Ви — провідні інженери компанії, що розробляє програмне забезпечення для інфраструктури сучасного мегаполісу. 

Ваше завдання — оцінити складність запропонованих рішень та обрати ті, що не «обвалять» сервери при зростанні кількості жителів.

📍 Завдання 1. Електронна черга в ЦНАП

Проблема: Система має видати номер талона для нового відвідувача.

• Алгоритм А: Програма переглядає список усіх виданих за день талонів (n), щоб знайти наступний вільний номер.

• Алгоритм Б: Програма зберігає останній виданий номер у спеціальній змінній і просто додає до нього 1.

Запитання інженера:

1. Визначте складність обох алгоритмів у O-нотації.

2. Який алгоритм працюватиме миттєво, навіть якщо за день прийде 1 000 000 людей?

💳 Завдання 2. Детектор викрадених карток

Проблема: Валідатор у метро має перевірити, чи не заблокована картка пасажира. У базі даних n заблокованих карток (масив не впорядкований).

• Рішення №1: Порівняти номер картки пасажира з кожним номером у «чорному списку» по черзі.

• Рішення №2: Використати алгоритм «бінарного пошуку» (але для цього список має бути заздалегідь відсортований).

Запитання інженера:

1. Яку складність має Рішення №1 (O(1), O(n) чи O(n2))?

2. Чому Рішення №1 може призвести до величезних черг у годину пік, якщо список заблокованих карток стане дуже великим?

📦 Завдання 3. Логістика кур'єрської служби

Проблема: Робот-кур'єр має n посилок. Йому потрібно порівняти вагу кожної посилки з вагою кожної іншої посилки в контейнері, щоб правильно збалансувати платформу.

• Код: Реалізовано через два вкладені цикли (для кожної посилки i ми переглядаємо всі посилки j).

Запитання інженера:

1. Яку складність має цей алгоритм?

2. Якщо кількість посилок збільшиться у 10 разів (з 10 до 100), у скільки разів зросте час роботи алгоритму? (Підказка: згадайте про n2).

⚡ Завдання 4. Енергетичний аудит (Пошук несправності)

Проблема: Є лінія електропередач із n ліхтарів. Потрібно знайти один несправний ліхтар.

• Сценарій: Ви проходите вздовж усієї лінії від 1-го до останнього ліхтаря.

Запитання інженера:

1. Яка складність цього процесу у найгіршому випадку?

2. Як зміниться складність (O), якщо ви точно знаєте, що несправний ліхтар завжди є третім від початку лінії?

🛠️ Підсумкова таблиця для самоперевірки (Чек-лист інженера)

Перегляньте таблицю, щоб перевірити свої розрахунки:

🏁 Рефлексія: «Code Review»

Після виконання завдань дайте відповідь на запитання:

«Якщо я напишу програму зі складністю O(n2), а мій колега — O(n), хто з нас отримає премію від замовника, коли кількість даних зросте до мільйона?»

📤 Як здати роботу

1. Збережіть усі файли та скриншоти.

2. Завантажте їх у розділ Ваші роботи на платформі Google ClassRoom.

За підручником

"Інформатика, 9 клас" (Й.Я. Ривкінд та їнші):

• • Прочитайте та розберіть теоретичний матеріал пункту 5.3 (стор. 265-267).

Для моніторингу засвоєння знань пройдіть тестування

• https://vseosvita.ua/test/start/bco026