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

Яке позначення описує нижню межу зростання?

1. Ao (мале o)
2. BΩ (велике Омега)
3. CO (велике O)
4. DΘ (велике Тета)

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

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

Яка часова складність сортування вставками в найкращому випадку, на вже відсортованому масиві?

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

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

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

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

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

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

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

Задача про рюкзак 0/1, розв'язана динамічним програмуванням, потребує O(nW) часу. Чому це називають псевдополіноміальним часом?

1. AТому що n завжди мале
2. BТому що алгоритм рандомізований, а його час роботи змінюється для кожних вхідних даних
3. CТому що він працює лише для W = 0
4. DW — число, тому час експоненційний відносно кількості бітів, використаних для запису W

Що випливало б, якби хтось знайшов поліноміальний алгоритм для однієї NP-повної задачі?

1. AПроблема зупинки стала б розв'язною
2. BУсі алгоритми з експоненційним часом негайно стали б працювати за лінійний час
3. CКожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP
4. DЛише ця одна задача перейшла б до P