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

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

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

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

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

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

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

Що означає, що задача має оптимальну підструктуру?

1. AЗадача має рівно один оптимальний розв'язок, спільний для кожної підзадачі
2. BЗадачу можна розв'язати за сталий час
3. CУсі підзадачі мають однаковий розмір
4. DОптимальний розв'язок можна побудувати з оптимальних розв'язків її підзадач

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

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

Розв'язком рекурентного співвідношення T(n) = 2T(n/2) + O(n) є:

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

Як алгоритм Беллмана–Форда виявляє цикл від'ємної ваги, досяжний із джерела?

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

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

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