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

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

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

Задачу зазвичай називають практично розв'язною (tractable), якщо:

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

Що означає, що операція виконується за час O(1)?

1. AВона обробляє рівно один елемент за секунду часу виконання
2. BЇї можна виконати лише один раз
3. CВона завжди триває рівно одну секунду
4. DЇї час виконання не зростає з розміром вхідних даних

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

Динамічне програмування корисне, коли задача має:

1. AПерекривні підзадачі та оптимальну підструктуру
2. BЛише випадкові вхідні дані
3. CЖодних підзадач, тож її можна розв'язати за один крок
4. DОдин цикл

Яка часова складність: for i = 1 to n: for j = 1 to i: виконати роботу O(1)?

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

Задача про рюкзак 0/1, розв'язана динамічним програмуванням, потребує O(nW) часу. Чому це називають псевдополіноміальним часом?

1. AТому що алгоритм рандомізований, а його час роботи змінюється для кожних вхідних даних
2. BW — число, тому час експоненційний відносно кількості бітів, використаних для запису W
3. CТому що він працює лише для W = 0
4. DТому що n завжди мале

Як співвідносяться n! і 2ⁿ для великих n?

1. An! є O(n²)
2. BВони зростають з однаковою швидкістю
3. Cn! зростає швидше, ніж 2ⁿ
4. D2ⁿ зростає швидше, ніж n!