Ця карта пояснює, як обчисли вартість алгоритму: скільки операцій він робить залежно від розміру даних, n, і як вона зростає, коли зростає n.
Вартість — функція від n. Секунди залежать від комп’ютера; операції — ні.
Натисни кожну рамку, щоб побачити її пояснення. Стрілки ← → (або кнопки внизу) переходять до наступного і Esc закриває його. Коли ти його побачив, з’являється ✓; натисни, щоб прибрати. Рамки з «?» належать іншим рівням.
Ця карта пояснює, як обчисли вартість алгоритму: скільки операцій робить програма. Кожна рамка має коротке пояснення і в деяких випадках вправу.
Алгоритм є швидкий коли робить менше операцій.
Натисни кожну рамку, щоб побачити її пояснення. Стрілки ← → переходять до наступного і Esc закриває його. Коли ти його побачив, з’являється ✓.
4 клас ESO (для обдарованих). Спрощена версія: правила обчислення, порядок відносно n і бінарний пошук. Без формальної нотації O(·), без графіків алгоритмів і без рамки операцій.
Пасує до: Цифровізація 4 класу (обчислювальне мислення: критерії 3.1 і 3.2, логічні та ефективні алгоритми).
Рекомендована вправа: порахувати операції циклу, а потім перевірити бінарним пошуком, скільки кроків він робить.
PTD-I · 1 клас бакалаврату. Додаються правила обчислення (послідовність, умова й цикл), нотація O(·), графіки зростання й часу, лінійний пошук і сортування вибором. Експерименти з часом (мс) більше не в центрі: вимірюється кількість операцій.
Пасує до: Програмування та обробка даних I: CEsp1 (аналіз і проєктування алгоритмів, критерій 1.3 щодо обчислювальної вартості) і CEsp3 (ефективність і складність операцій у структурах даних).
Рекомендована вправа: за 10⁹ операцій за секунду і n = 10⁶ обчислити, скільки часу знадобилося б лінійному пошуку (n) і бульбашковому (n(n−1)/2), і порівняти з графіком часу.
PTD-II · 2 клас бакалавату. Той самий зміст, що й у PTD-I: правила обчислення, нотація O(·), графіки зростання та алгоритми пошуку й сортування.
Пасує до: Програмування та обробка даних II: CEsp1 (алгоритми та обчислювальне мислення).
Рекомендована вправа: порівняти вручну лінійний і бінарний пошук з n = 1 000 000 і обґрунтувати різницю.
Рамки з «?» приховані на цьому рівні: одне натискання їх відкриває і показує зв’язок, інше відкриває вікно, а після перегляду ще одне знову їх ховає. Кнопка 🔗 копіює посилання з рівнем і відкритими рамками.
Перемикач Рівень змінює карту та всі вікна. В адресі зберігається рівень (?edad=4eso, ptd1 або ptd2) і відкриті рамки (&ver=casos,fonts).
Коли кажемо, що алгоритм швидкий, треба сказати, у чому саме швидкий. Секунди залежать від комп’ютера, системи і того, що виконується. Тому ми рахуємо операцій.
Коли порівнюєш два алгоритми, запитай себе: що зростає і наскільки?
Обчислювальна вартість вимірює роботу програми залежно від розміру даних (n. Зверни увагу на дві речі: на час (кількість операцій) і пам’ять (скільки місця вона займає).
Обчислювальна вартість алгоритму — це кількістьелементарних операцій що робить залежно від розміру даних, n. Секунди залежать від комп’ютера; операції — ні.
Елементарна операція (присвоєння, додавання, порівняння або доступ до позиції) коштує 1. Рахують найгірший випадок, що гарантує результат для будь-яких даних.
| Функція T(n) | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| n | 10 | 1 000 | 1 000 000 |
| n² | 100 | 1 000 000 | 1 000 000 000 000 |
Секунди не годяться для порівняння алгоритмів. Рахуй операцій і подивися, як зростають коли зростає n.
Розмір n. Усі формули залежать від розміру, n: кількість даних, які отримує алгоритм. Визнач n перед підрахунком (кількість елементів, цифр або рядків — залежно від задачі).
Програма виконує інструкції одна за одною. Щоб обчислити вартість, додай інструкції. Якщо є цикл, помнож на кількість повторень.
Проста інструкція коштує 1. Цикл множить вартість свого тіла на кількість повторень.
Програма поєднує чотири структури. Загальна вартість обчислюється застосуванням правила до кожної.
| Структура | Правило вартості | Приклад |
|---|---|---|
| Проста інструкція | 1 | x ← x + 1 → 1 |
| Послідовність | сума вартостей | A; потім B → T(A) + T(B) |
| Умова | перевірка + найдорожча гілка | якщо … то … інакше … → 1 + максимум(T₁, T₂) |
| Цикл | ітерації × вартість тіла | для i від 1 до n: x ← x + 1 → n |
Коли не знаєш, яка гілка умови виконається, бери найдорожчу: це найгірший випадок.
Вартість циклу — це вартість його тіла, помножена на кількість повторень. Одну операцію не помітиш; мільйон — помітиш.
| Структура | Операції з n = 1 000 | Операції з n = 1 000 000 |
|---|---|---|
| Цикл | 1 000 | 1 000 000 |
| Два вкладені цикли | 1 000 000 | 1 000 000 000 000 |
Порахуй, скільки разів виконується найвнутрішніше тіло. Цикл із n кроків робить n операцій; два вкладені цикли з n кроками роблять n · n.
Два вкладені цикли це O(n²); цикл, O(n).
Структура, що здається простою («це просто цикл»), може приховувати пошук усередині. Завжди дивись, що є всередині циклу.
Цикл повторює своє тіло. Загальна вартість — це вартість тіла, помножена на кількість повторень.
| Структура | Операції з n = 1 000 | Операції з n = 1 000 000 |
|---|---|---|
| Цикл | 1 000 | 1 000 000 |
| Два вкладені цикли (n · n) | 1 000 000 | 1 000 000 000 000 |
| Два цикли, другий до i | 500 500 | 500 000 500 000 |
Цикл є O(n). Два вкладені цикли це O(n²). Вкладені цикли, що йдуть до i, роблять n(n+1)/2 кроків: також O(n²), бо ми ігноруємо константу ½.
Структура, що здається простою («це просто цикл»), може приховувати пошук усередині. Завжди дивись, що є всередині циклу.
Бульбашкове сортування порівнює сусідів і міняє їх місцями, якщо вони стоять не по порядку. Повторює проходи, доки не перестане щось міняти. Це типовий алгоритм, щоб зрозуміти вартість, бо можна полічити все.
| n (дані) | Порівняння (найгірший випадок) | Обміни (середнє) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
Кожен прохід ставить найбільше значення в кінець. За n даних перший прохід робить n−1 порівнянь, наступний n−2, і так далі до 1. Разом у найгіршому випадку: n(n−1)/2.
Зверни увагу: якщо помножиш дані на 10, робота множиться на 100.
Це є O(n²). Порівняння зростають як квадрат n.
Бульбашкове сортування порівнює кожну пару сусідів і міняє місцями ті, що стоять не по порядку. Після кожного проходу найбільше значення опиняється в кінці.
| n (дані) | Порівняння (найгірший випадок) | Обміни (середнє) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
Перший прохід робить n−1 порівнянь, другий n−2, і так далі до 1. Разом у найгіршому випадку: (n−1) + (n−2) + … + 1 = n(n−1)/2, тобто O(n²).
Графік часу: час пропорційний кількості операцій. За 10⁹ операцій за секунду 10⁶ операцій займають 1 мс.
Якщо список впорядкований, не треба дивитися весь. Дивишся на середину і відкидаєш половину, яка не може містити шукане. Кожен крок зменшує розмір удвічі.
Список — це 1, 2, 3… n: зберігати його повністю в пам’яті не потрібно, тому можна перевірити з 1 000 000 000.
| n (дані) | Кроки бінарного (найгірший випадок) | Порівняння лінійного (найгірший випадок) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Кожен крок робить одне порівняння й відкидає половину. Кроків приблизно log₂ n. Тому 1 000 000 000 даних потребують лише 30 кроків.
Це є O(log n).
Бінарний пошук працює лише тоді, коли список впорядкований. Її сортування також має свою ціну.
Бінарний пошук дивиться на середину впорядкованого списку і відкидає половину, яка не може містити шукане. Кожен крок ділить на 2.
Список — це 1, 2, 3… n. Рахуються лише кроки: зберігати його в пам’яті не потрібно.
| n (дані) | Кроки (найгірший випадок) | Лінійний пошук (найгірший випадок) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Кожен крок зменшує розмір удвічі: після k кроків залишається n / 2ᵏ елементів. Оскільки n / 2ᵏ = 1, коли k = log₂ n, вартість становить O(log n).
Бінарний пошук працює лише тоді, коли список впорядкований. Її сортування також має свою ціну.
Графік часу: час пропорційний кількості операцій. За 10⁹ операцій за секунду 10⁶ операцій займають 1 мс.
Коли дані зростають, вартість зростає з певною швидкістю. Нотація O(·) зберігає лише цей темп і ігнорує константи.
O(log n) зростає дуже повільно: коли n переходить від 1 до 20, він досягає лише ≈ 4,3, тоді як O(n) досягає 20.
За малого n усі криві здаються близькими; з n ≈ 10 квадратична відокремлюється від інших.
| Функція | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| O(log n) | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) | 10 | 1 000 | 1 000 000 |
| O(n log n) | ≈ 33 | ≈ 10 000 | ≈ 20 000 000 |
| O(n²) | 100 | 1 000 000 | 1 000 000 000 000 |
O(1): вартість не залежить від n. O(log n): кожен крок ділить на 2 (бінарний). O(n): пропорційна до n (лінійний пошук). O(n log n): типова для добрих алгоритмів сортування. O(n²): два вкладені цикли (бульбашкове, сортування вибором).
Коли n множиться на 10: при O(n) вартість множиться на 10; при O(n²) — на 100; при O(log n) майже не змінюється.
Ігноруй константи й малі члени: 3n² + 5n це O(n²).
Порядок відносно n пояснює, як зростає вартість, коли зростають дані. Це найважливіша ідея цієї карти.
Коли n множиться на 10, вартість O(n) також множиться на 10, а вартість O(n²) — на 100.
Якщо вартість O(n), робота зростає так само, як дані. Якщо O(n²), то при подвоєнні даних робота збільшується вчетверо.
Важливо як зростає, а не точну кількість операцій.
Той самий алгоритм може працювати довше чи коротше залежно від даних. Тому аналіз розрізняє три випадки: найкращий, середній і найгірший.
| Випадок | Бульбашкове сортування | Бінарний |
|---|---|---|
| Найкращий | n−1 порівнянь (список уже впорядкований) | 1 крок (середина — це шуканий елемент) |
| Середній | ≈ n²/2 порівнянь | ≈ log₂ n кроків |
| Найгірший | n(n−1)/2 порівнянь | ⌊log₂ n⌋ + 1 кроків |
Якщо частка близька до 2, зростання приблизно лінійне; якщо близька до 4 — квадратичне. Шум браузера не дає точності, тому беруть медіану з 3 повторень.
Щоб оцінити алгоритм, треба подивитися на дані найгірший випадок (ті, що найбільше його навантажують), але також середній випадок, який зазвичай є найпоширенішим.
Одне вимірювання конкретного випадку не покаже, який найгірший. Спочатку проаналізуй випадок, а потім вимірюй.
Лінійний пошук перевіряє елементи один за одним, доки не знайде шукане. Це найпростіший метод, і він слугує еталоном для порівняння з бінарним пошуком.
Кожен елемент порівнюється зі шуканим значенням, доки його не знайдуть або не дійдуть до кінця.
| Випадок | Порівняння | З n = 1 000 000 |
|---|---|---|
| Найкращий (це перший) | 1 | 1 |
| Середній (він посередині) | n / 2 | 500 000 |
| Найгірший (він останній або його немає) | n | 1 000 000 |
Вартість — O(n): кожен елемент перевіряється щонайбільше один раз.
Коли називаєш вартість, скажи який випадок це: найкращий, середній або найгірший.
Графік часу: час пропорційний кількості операцій. За 10⁹ операцій за секунду 10⁶ операцій займають 1 мс.
Сортування вибором шукає мінімум у невпорядкованій частині й ставить його попереду. Повторюй, доки весь список не буде впорядкований.
Перший прохід шукає мінімум серед n елементів (n−1 порівнянь) і ставить його на першу позицію. Наступний шукає серед n−1 елементів і так далі до останнього.
| n (дані) | Порівняння (завжди) |
|---|---|
| 10 | 45 |
| 100 | 4 950 |
| 1 000 | 499 500 |
Разом: (n−1) + (n−2) + … + 1 = n(n−1)/2, тобто O(n²) у всіх випадках. Робить щонайбільше n−1 обмінів.
Сортування вибором завжди робить ті самі порівняння; бульбашкове може зупинитися раніше, якщо список уже впорядкований.
Графік часу: час пропорційний кількості операцій. За 10⁹ операцій за секунду 10⁶ операцій займають 1 мс.
Сортування вставкою бере кожен елемент і ставить його на належне місце у вже впорядкованій частині.
У найгірший випадок (обернений список) робить n(n−1)/2 порівнянь: O(n²). У найкращий випадок (вже впорядкований список) робить лише n−1: O(n).
Сортування вставкою швидке, коли список уже майже впорядкований.
Сортування злиттям ділить список навпіл, сортує кожну половину і потім їх зливає.
Кожен рівень поділів робить n кроків, а рівнів log₂ n. Вартість становить O(n log n) у всіх випадках.
Для великих списків вона значно швидша за бульбашкове.
Вимірювати легко помилитися. Ось найпоширеніші помилки і як їх уникнути.
Перш ніж казати, що алгоритм швидший, запитай себе: з якими даними, на якому комп’ютері і скільки разів я це вимірював.
Прочитай кожну ситуацію і вибери яке поняття пояснює випадок. Якщо ти виберете той, що теж є, але не є головним, ми тобі скажемо.
Програма складає 1 000 000 чисел у циклі. Яке поняття пояснює, чому вартість висока?
Програма складає 1 000 000 чисел у циклі. Яке поняття пояснює, чому вартість висока?
Ти шукаєш число 42 у впорядкованому списку з мільйона чисел. Дивишся на середину, відкидаєш половину і приблизно за 20 кроків знаходиш його. Який це алгоритм?
Алгоритм проходить список, порівнює сусідів і міняє їх місцями. Зі зворотним списком він робить n(n−1)/2 порівнянь. Який це алгоритм?
Алгоритм працює в 4 рази довше, коли ти подвоюєш дані. Яке поняття описує, як зростає його вартість?
Ти шукаєш число в невпорядкованому списку з n елементів і порівнюєш його з кожним елементом, доки не знайдеш. Який це алгоритм?
Алгоритм шукає мінімум у невпорядкованій частині й ставить його попереду. Він робить n(n−1)/2 порівнянь, навіть якщо список уже впорядкований. Який це алгоритм?
Ця карта об’єднує класичні поняття аналізу алгоритмів і цілі навчальної програми Балеарських островів. Тут ти можеш це перевірити та поглибити знання.