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

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

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

Чому дорівнює log₂ 1024?

1. A12
2. B10
3. C512
4. D32

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

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

Чи правильно казати, що алгоритм O(n²) є також O(n³)?

1. AНі, бо «велике O» завжди має вказувати точну швидкість зростання функції
2. BНі, бо для великих n n³ менше за n²
3. CТак, але лише якщо n менше за 100
4. DТак, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³

Який розв'язок рекурентного співвідношення T(n) = T(n − 1) + O(1)?

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

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

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

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

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

Множення Карацуби задовольняє T(n) = 3T(n/2) + O(n). Який розв'язок?

1. AΘ(n^{log₂ 3}), близько n^1,585
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n³)