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

Доступ до елемента масиву за індексом займає:

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

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

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

Як працює сортування вибором?

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

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

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

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

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

Який алгоритм сортування є стійким?

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

Найкоротші прості шляхи можна знайти за поліноміальний час. Що відомо про пошук найдовшого простого шляху між двома вершинами в загальному графі?

1. AЇї можна розв'язати алгоритмом Дейкстри з від'ємними вагами
2. BВона нерозв'язна
3. CЦе NP-складна задача
4. DЇї завжди можна розв'язати за O(V + E)

Що встановила теорема Кука–Левіна?

1. AКожну задачу з NP можна розв'язати за експоненційний час
2. BЗадача виконуваності булевих формул (SAT) є NP-повною
3. CПроблема зупинки нерозв'язна
4. DP не дорівнює NP