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

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

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

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

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

Що з наведеного зростає найповільніше зі збільшенням n?

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

Динамічне програмування корисне, коли задача має:

1. AПерекривні підзадачі та оптимальну підструктуру
2. BЛише випадкові вхідні дані
3. CОдин цикл
4. DЖодних підзадач, тож її можна розв'язати за один крок

Що вимірює амортизований аналіз?

1. AВартість однієї найдорожчої операції будь-де в послідовності
2. BСередню вартість операції на послідовності операцій у найгіршому випадку
3. CОчікувану вартість на випадкових вхідних даних
4. DВартість алгоритму на найкращих вхідних даних

Часова складність наївного рекурсивного обчислення чисел Фібоначчі (fib(n) = fib(n−1) + fib(n−2)) є:

1. AЕкспоненційною
2. BЛогарифмічною
3. CСталою
4. DЛінійною

Сортування вставками працює за O(n) на відсортованих даних. Чи суперечить це нижній межі Ω(n log n) для сортування порівняннями?

1. AНі, нижня межа стосується найгіршого випадку серед усіх вхідних даних, а не кожних вхідних даних
2. BТак, отже, нижня межа хибна
3. CТак, але лише для масивів, коротших за 100
4. DНі, бо сортування вставками не є сортуванням порівняннями

Чому будь-який пошук порівняннями у відсортованому масиві потребує Ω(log n) порівнянь у найгіршому випадку?

1. AДерево рішень з n можливими результатами має глибину щонайменше log₂ n
2. BКожне порівняння триває логарифмічний час
3. CКожен елемент треба порівняти щонайменше один раз
4. DБінарний пошук — єдиний можливий алгоритм, і йому потрібно log₂ n порівнянь