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

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

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

Який клас складності зростає найшвидше для великих n?

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

Які три кроки алгоритму «розділяй і володарюй»?

1. AВгадати, перевірити, повторити
2. BПрочитати, обчислити, записати
3. CРозділити, підкорити, об'єднати
4. DВідсортувати, знайти, повернути

Яка часова складність: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

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

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

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

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

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

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