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

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

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

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

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

Скільки додаткової пам'яті використовує стандартне сортування злиттям на основі масиву?

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

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

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

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

Як алгоритм Прима будує мінімальне кістякове дерево?

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

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

1. AВиконуваність схем
2. B2-SAT, де кожен диз'юнкт має щонайбільше два літерали
3. CЗагальна SAT для формул у кон'юнктивній нормальній формі
4. D3-SAT, де кожен диз'юнкт має рівно три літерали

Сортування вставками працює за O(n) на відсортованих даних. Чи суперечить це нижній межі Ω(n log n) для сортування порівняннями?

1. AТак, але лише для масивів, коротших за 100
2. BНі, нижня межа стосується найгіршого випадку серед усіх вхідних даних, а не кожних вхідних даних
3. CНі, бо сортування вставками не є сортуванням порівняннями
4. DТак, отже, нижня межа хибна