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

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

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

Яка часова складність сортування вставками в найкращому випадку, на вже відсортованому масиві?

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

Як називається зростання O(2ⁿ)?

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

Яка часова складність стандартного алгоритму динамічного програмування для найдовшої спільної підпослідовності рядків довжиною m і n?

1. AO(mn log n)
2. BO(2^m+n)
3. CO(mn)
4. DO(m + n)

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

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

Нижня межа для сортування на основі порівнянь у найгіршому випадку становить:

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

Яке визначення класу NP правильне?

1. AЗадачі, які не може розв'язати жоден алгоритм
2. BЗадачі, які неможливо розв'язати за поліноміальний час
3. CЗадачі, що не є поліноміальними
4. DЗадачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката

Як алгоритм Беллмана–Форда виявляє цикл від'ємної ваги, досяжний із джерела?

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