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

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

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

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

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

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

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

Ви один раз сортуєте масив із n елементів, а потім відповідаєте на k запитів про належність бінарним пошуком. Яка загальна вартість?

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

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

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

Швидке сортування завжди бере опорним перший елемент. На яких вхідних даних воно демонструє поведінку найгіршого випадку?

1. AНа вже відсортованому масиві
2. BНа масиві, всі елементи якого різні
3. CНа масиві довжини 2
4. DНа масиві у випадковому порядку

Що треба зробити, щоб показати, що нова задача X є NP-складною?

1. AЗвести X до відомої NP-складної задачі за поліноміальний час
2. BПоказати, що X можна перевірити за поліноміальний час
3. CПоказати, що X не має поліноміального алгоритму для малих вхідних даних
4. DЗвести відому NP-складну задачу до X за поліноміальний час

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

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