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

Який із цих часів виконання є поліноміальним?

1. AO(nⁿ)
2. BO(n³)
3. CO(n!)
4. DO(2ⁿ)

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

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

Просторова складність вимірює:

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

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

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

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

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

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

1. AБлизько 1,000
2. BБлизько 500,000
3. CБлизько 100
4. DБлизько 20

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

1. AΘ(n log n)
2. BΘ(n)
3. CΘ(n²)
4. DΘ(n log² n)

Чому пошук у геш-таблиці в середньому має складність O(1), а в найгіршому випадку — O(n)?

1. AБагато ключів через колізії можуть потрапити в один і той самий кошик
2. BДоступ до масивів має складність O(n)
3. CКлючі спершу потрібно відсортувати
4. DГеш-функції повільні