Робочий аркуш «Алгоритми та складність» з відповідями

Яка часова складність пошуку найбільшого значення в невідсортованому масиві з n чисел?

1. AO(1)
2. BO(n)
3. CO(n log n)
4. DO(log n)

Що таке базовий випадок рекурсивної функції?

1. AВипадок, на який відповідають безпосередньо, без нового рекурсивного виклику
2. BВипадок із найбільшими вхідними даними, який обробляється до будь-яких рекурсивних викликів
3. CВиклик, що використовує найбільше пам'яті
4. DПерший рядок функції

Доступ до елемента масиву за індексом займає:

1. AO(n²)
2. BO(1)
3. CO(n)
4. DO(log n)

Як алгоритм Прима будує мінімальне кістякове дерево?

1. AВін вирощує одне дерево від початкової вершини, додаючи найдешевше ребро, що виходить із дерева
2. BВін запускає пошук у ширину й зберігає дерево BFS
3. CВін видаляє найдорожче ребро, доки не залишиться циклів
4. DВін сортує всі ребра за вагою й додає кожне, окрім тих, що утворили б цикл у лісі

Який час виконання порозрядного сортування LSD для n цілих чисел із d цифрами в системі числення з основою k?

1. AO(dn log k)
2. BO(n²)
3. CO(d(n + k))
4. DO(n log n)

Чому основу логарифма в «великому O» зазвичай не вказують, як-от в O(log n)?

1. AУсі логарифми в інформатиці мають основу 10, тож вона мається на увазі
2. BЛогарифми завжди округлюють до цілих
3. CЛогарифми з різними основами відрізняються лише сталим множником
4. DОснова має значення лише для малих n

Задача є NP-повною, якщо вона:

1. AРозв'язна за поліноміальний час
2. BНерозв'язна
3. CНалежить до NP і будь-яка задача з NP зводиться до неї за поліноміальний час
4. DЛежить поза NP, але складніша за всі задачі NP, як-от проблема зупинки

Яке твердження про P і NP є правильним?

1. ANP означає «неполіноміальний» (not polynomial)
2. BКожна задача з P також належить до NP
3. CДоведено, що P ≠ NP
4. DРозв'язки задач NP неможливо швидко перевірити