Безкоштовні тестові питання з теми Алгоритми та складність з підказками й поясненнями, трьох рівнів: ключові терміни й факти, застосування понять, кейси та аналіз.
Який клас складності зростає найшвидше для великих n?
Чудова робота. Хочете наступну?Готові до наступної? 5 нових задач щодня в кожній темі.
Алгоритм — це скінченний перелік точних кроків, що розв’язує задачу, наприклад сортування списку чи пошук прізвища в телефонній книзі.
Два алгоритми можуть розв’язувати ту саму задачу, але витрачати дуже різний час. Складність описує, як обсяг роботи зростає, коли вхідні дані збільшуються.
Розмір входу позначають n: кількість елементів для сортування, довжина списку, кількість вузлів графа.
Уявіть пошук прізвища в телефонній книзі на 1000 сторінок. Прочитати кожну сторінку — до 1000 кроків. Відкрити посередині й щоразу ділити навпіл — близько 10 кроків.
Часова складність рахує кроки. Просторова складність рахує додаткову пам’ять. Обидві записують як функцію від n.
Зазвичай розглядають найгірший випадок: найбільший обсяг роботи серед усіх входів розміру n. Іноді питають про середній або найкращий випадок.
Відповідь: 4 секунди. Подвоєння n множить n² на 2² = 4, тож час зростає приблизно з 1 до 4 секунд. 2 секунди були б відповіддю для лінійного зростання, а 8 — для n³.
Позначення велике O зберігає лише те, що важливо для великих n. Ви відкидаєте сталі множники й залишаєте лише доданок, що зростає найшвидше.
Для n = 1000 доданок n² дорівнює 3 000 000, тоді як 5n — лише 5000. Менші доданки майже не змінюють суми.
Ці класи повторюються знову й знову, від найповільнішого до найшвидшого зростання:
Велике O — це верхня межа: робота зростає щонайбільше так швидко. Ω (велика омега) — нижня межа, а Θ (велика тета) — точна межа, і верхня, і нижня.
Основа логарифма у великому O не має значення, бо логарифми з різними основами відрізняються лише сталим множником.
Відповідь: O(n²). Для великих n домінує доданок n², а сталий множник 2 відкидають. O(n) залишає хибний доданок, а O(2n²) забуває відкинути сталу.
Кілька алгоритмів трапляються майже в кожному курсі. Вивчіть їхню складність як факти.
Рекурсивна функція викликає сама себе на меншому вході, доки не досягне базового випадку, на який відповідає безпосередньо. Її час роботи записують як рекурентне співвідношення:
Варто знати три ідеї проєктування. Розділяй і володарюй розбиває, розв’язує й поєднує. Жадібний алгоритм на кожному кроці обирає локально найкращий варіант. Динамічне програмування зберігає відповіді на перекривні підзадачі, щоб обчислювати їх один раз.
Відповідь: O(n²). За поганих опорних елементів кожне розбиття залишає n − 1 елементів з одного боку, що дає O(n²). O(n log n) — його середній випадок і найгірший випадок сортування злиттям.
Щоб знайти часову складність фрагмента коду:
Для теоретичного запитання спершу назвіть алгоритм або ідею, яку воно описує, потім пригадайте її складність і умови (відсортований вхід, невід’ємні ваги, перекривні підзадачі).
Простежте кожен крок. Спробуйте передбачити наступний, перш ніж його відкрити.
Яка часова складність цього коду? for i = 1 to n: (j = 1; while j < n: j = j × 2)
n — це число, до якого виконуються цикли.
i іде від 1 до n з кроком 1, тож зовнішній цикл виконується n разів.
j набуває значень 1, 2, 4, 8, … і зупиняється, досягнувши n. Після k ітерацій j = 2k, тож цикл зупиняється приблизно після log₂ n ітерацій.
Внутрішній цикл розташований усередині зовнішнього, тож кількості множаться.
Для n = 1024 внутрішній цикл виконується log₂ 1024 = 10 разів, тож тіло виконується 1024 · 10 = 10 240 разів. Це набагато менше за n² = 1 048 576.
O(n log n)
Відповідь: O(n). Цикли один за одним додаються: n + n = 2n, і стала відкидається, тож O(n). O(n²) було б правильним, лише якби один цикл був усередині іншого.
P містить задачі, які можна розв’язати за поліноміальний час. NP містить задачі, розв’язки яких можна перевірити за поліноміальний час. Кожна задача з P належить до NP; чи P = NP, досі невідомо.
Вивчайте крок за кроком у застосункуВивчайте крок за кроком у застосунку
Яка нотація описує верхню межу зростання?
O задає верхню межу, Ω — нижню межу, а Θ — точну (асимптотично щільну) межу.
У відсортованому масиві ви шукаєте два елементи із заданою сумою, рухаючи по одному вказівнику з кожного кінця всередину. Яка часова складність?
Якщо сума замала, лівий вказівник рухається праворуч, якщо завелика — правий рухається ліворуч, тож кроків щонайбільше n.
Алгоритм Штрассена множить матриці, використовуючи 7 замість 8 рекурсивних множень блоків половинного розміру. Який його час виконання?
За a = 7 і b = 2 nlog₂ 7 домінує над роботою додавання O(n²), що дає близько n2,81.
Два алгоритми можуть розв’язувати ту саму задачу, але витрачати дуже різний час. Складність описує, як обсяг роботи зростає, коли вхідні дані збільшуються.
Розмір входу позначають n: кількість елементів для сортування, довжина списку, кількість вузлів графа.
Кожне питання має чотири варіанти відповіді, і лише один правильний. Застрягли? Спершу відкрийте невелику підказку, а повне пояснення — лише коли воно знадобиться.