Модуль 9 · Урок 33 із 58
Algorithm contract: Big O, time і space complexity
Швидкість на одному ноутбуці не є складністю алгоритму. Спочатку визначають input size, домінантну операцію та гіпотезу росту; лише потім запускають вимірювання й пояснюють, що саме вони доводять.
Безпечна algorithm-практика модуля 9
Пакет містить тільки synthetic tasks і graph, deterministic operation counts, локальний Python CLI, tests та read-only verifier. Жодних персональних чи production-даних, credentials, мережевих викликів, machine paths або зовнішніх залежностей.
Алгоритм починається з контракту
Algorithm contract описує допустимий input, очікуваний output, invariant, failure policy і ресурсну межу. Без цього фраза «працює швидко» порожня: пошук одного ID, сортування всіх записів і побудова всіх пар мають різний розмір задачі та різні домінантні операції.
Big O описує ріст, а не секундомір
O(1), O(log n), O(n), O(n log n) і O(n²) порівнюють порядок росту за збільшення input. Константи та середовище важливі для latency, але не змінюють клас росту. Два вкладені цикли не автоматично означають O(n²): треба бачити, скільки разів реально виконується inner operation.
| Pattern | Cost hypothesis | Перевірка |
|---|---|---|
| Direct indexed access | O(1) | Одна адресована операція |
| Halve search range | O(log n) | Інтервал зменшується приблизно вдвічі |
| Visit every row | O(n) | Один visit на елемент |
| Sort all rows | O(n log n) | Документований algorithm contract |
| Compare every pair | O(n²) | Кількість пар росте квадратично |
Average, worst і amortized — різні твердження
Для dict і set average lookup за добрих hash assumptions відрізняється від worst case. Для list.append окреме розширення backing array може бути дорожчим, але amortized cost розподіляє рідкісні resize по багатьох append. У звіті треба назвати режим, а не залишати голе O(1).
Не обіцяйте implementation-independent константи
Python implementations і версії можуть мати різні constant factors та деталі. Контракт курсу стосується вибраних операцій і задокументованих властивостей, а benchmark завжди містить runtime, input і метод.
Space complexity і hidden copies
Новий sorted(), slice, materialized generator або дубльований index можуть вимагати додаткову пам’ять. In-place зміна теж має ціну: вона змінює ownership contract і може зламати caller. Тому рішення оцінюють парою time + auxiliary space, а також ясністю й коректністю.
- Назвіть
nі важливі додаткові параметри, наприкладk. - Виберіть домінантну операцію та порахуйте її.
- Опишіть best/average/worst лише там, де це має сенс.
- Зафіксуйте auxiliary allocations і mutation policy.
- Перевірте result на boundaries до розмови про performance.
Measurement не замінює reasoning
timeit прибирає частину типових пасток коротких вимірювань, але результат залежить від machine load, Python build, data distribution, warmup і setup. Для навчального lab спочатку використовується deterministic operation count, а timing — лише додатковий, не сертифікаційний доказ.
Методичні джерела
Урок, сценарії, пояснення й вправи створені SEOWORK. Посилання ведуть лише на офіційну документацію та Python Wiki.
Закріпіть матеріал уроку
Три сценарні питання. Для зарахування уроку потрібно дати щонайменше дві правильні відповіді.