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

Що з наведеного зростає найповільніше зі збільшенням n?

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

Яка нотація описує верхню межу зростання?

1. AВелике Тета
2. BВелике O
3. CМале омега
4. DВелике Омега

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

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

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

1. AO(V × E)
2. BO(V³ × E)
3. CO(V + E)
4. DO(E log V)

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

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

Чому багато бібліотечних процедур сортування переходять на сортування вставками для дуже малих підмасивів?

1. AСортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
2. BСортування вставками має складність O(n log n) у найгіршому випадку
3. CСортування вставками використовує менше пам'яті, ніж будь-який інший алгоритм сортування, на великих даних
4. DРекурсивні алгоритми не можуть обробляти масиви менші за 10 елементів

Який розв'язок рекурентного співвідношення T(n) = 2T(n/2) + n log n?

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

Яка часова складність побудови бінарної купи з n невідсортованих елементів висхідним методом (bottom-up)?

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