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

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

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

Яку складність зазвичай має алгоритм із двома вкладеними циклами, кожен із яких виконується n разів?

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

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

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

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

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

Жадібний алгоритм:

1. AЗавжди дає оптимальний розв'язок
2. BВикористовує лише рекурсію
3. CНа кожному кроці робить локально найкращий вибір
4. DПеребирає всі можливі розв'язки

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

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

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

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

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

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