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

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

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

Що таке алгоритм?

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

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

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

Чому динамічне програмування не дає реального пришвидшення для сортування злиттям?

1. AДинамічне програмування працює лише на задачах про графи, а не на масивах
2. BСортування злиттям уже має складність O(n)
3. CЙого підзадачі не перекриваються, тож нічого використати повторно
4. DСортування злиттям не має рекурсивної структури

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

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

Скільки пам'яті стека використовує проста рекурсивна функція факторіала fact(n) = n × fact(n − 1)?

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

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

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

Як класифікують задачу комівояжера?

1. AВерсія розпізнавання є NP-повною, а оптимізаційна версія — NP-складною
2. BВерсія розпізнавання належить до P, а оптимізаційна — NP-повна
3. CВона нерозв'язна
4. DВона належить до P, бо її розв'язує алгоритм Дейкстри, відвідуючи кожне місто один раз