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

Що означає f(n) = Θ(g(n))?

1. Af завжди менша за g для кожного n, тож g обмежує її зверху, але ніколи знизу
2. Bf зростає строго швидше, ніж g
3. Cf зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
4. Df зростає строго повільніше, ніж g

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

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

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

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

Часова складність наївного рекурсивного обчислення чисел Фібоначчі (fib(n) = fib(n−1) + fib(n−2)) є:

1. AЛінійною
2. BЕкспоненційною
3. CЛогарифмічною
4. DСталою

Пошук у ширину в незваженому графі знаходить:

1. AНайкоротші шляхи (за кількістю ребер) від початкової вершини
2. BТопологічний порядок у будь-якому графі
3. CНайкоротші шляхи в графах, що містять ребра з від'ємними вагами
4. DМінімальне кістякове дерево

Розв'язком рекурентного співвідношення T(n) = 2T(n/2) + O(n) є:

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

Топологічне сортування можливе лише для:

1. AНеорієнтованих графів
2. BПовних графів
3. CГрафів із від'ємними вагами
4. DОрієнтованих ациклічних графів

Яка часова складність: for i = 1 to n: for (j = i; j ≤ n; j = j + i) виконати роботу O(1)?

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