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

Цикл починається з i = 1 і подвоює i на кожній ітерації, доки i > n. Скільки ітерацій він виконує?

1. AБлизько n / 2
2. BБлизько n²
3. CБлизько log₂ n
4. DБлизько n

Який із цих часів виконання є поліноміальним?

1. AO(n³)
2. BO(2ⁿ)
3. CO(nⁿ)
4. DO(n!)

Скільки додаткової пам'яті використовує стандартне сортування злиттям на основі масиву?

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

Яка амортизована часова складність додавання елемента в кінець динамічного масиву, який подвоює свою місткість у разі заповнення?

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

Що обчислює алгоритм Флойда–Воршелла і як швидко?

1. AНайкоротші шляхи між усіма парами вершин за O(V³)
2. BМінімальне кістякове дерево за O(E log V)
3. CНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)
4. DТопологічний порядок за O(V²)

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

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

Чи належить 2²ⁿ до O(2ⁿ)?

1. AНі, бо 2²ⁿ = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено
2. BТак, бо сталі множники в показнику степеня в нотації «велике O» завжди ігноруються
3. CТак, бо обидві функції експоненційні
4. DНі, бо 2²ⁿ зростає повільніше, ніж 2ⁿ

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

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