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

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

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

Алгоритм O(n²) працює 1 секунду для n = 1000. Приблизно скільки він працюватиме для n = 2000?

1. A2 секунди
2. B8 секунд
3. C1 секунду
4. D4 секунди

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

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

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

1. AO(V + E)
2. BO(V³ × E)
3. CO(E log V)
4. DO(V × E)

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

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

Який алгоритм сортування є стійким?

1. AПірамідальне сортування
2. BШвидке сортування (типова версія на місці)
3. CСортування злиттям
4. DСортування вибором (типова версія)

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

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

Алгоритм Штрассена множить матриці, використовуючи 7 замість 8 рекурсивних множень блоків половинного розміру. Який його час виконання?

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