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

Що описує час виконання в середньому випадку?

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

Що описує час виконання алгоритму в найгіршому випадку?

1. AОчікуваний час на випадкових вхідних даних розміру n
2. BЧас на повільному комп'ютері
3. CЧас на найменших вхідних даних
4. DМаксимальний час на всіх вхідних даних розміру n

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

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

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

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

Чому основу логарифма в «великому O» зазвичай не вказують, як-от в O(log n)?

1. AЛогарифми завжди округлюють до цілих
2. BУсі логарифми в інформатиці мають основу 10, тож вона мається на увазі
3. CОснова має значення лише для малих n
4. DЛогарифми з різними основами відрізняються лише сталим множником

Нижня межа для сортування на основі порівнянь у найгіршому випадку становить:

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

Як класифікують задачу комівояжера?

1. AВона належить до P, бо її розв'язує алгоритм Дейкстри, відвідуючи кожне місто один раз
2. BВона нерозв'язна
3. CВерсія розпізнавання є NP-повною, а оптимізаційна версія — NP-складною
4. DВерсія розпізнавання належить до P, а оптимізаційна — NP-повна

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

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