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

Яку складність зазвичай має алгоритм із двома вкладеними циклами, кожен із яких виконується n разів?

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

Що таке рекурсія?

1. AМетод сортування
2. BЦикл, який ніколи не закінчується
3. CФункція, яка викликає саму себе для менших вхідних даних
4. DТип структури даних

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

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

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

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

Що обчислює алгоритм Флойда–Воршелла і як швидко?

1. AМінімальне кістякове дерево за O(E log V)
2. BТопологічний порядок за O(V²)
3. CНайкоротші шляхи між усіма парами вершин за O(V³)
4. DНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)

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

1. AБлизько 100
2. BБлизько 500,000
3. CБлизько 1,000
4. DБлизько 20

Який час виконання алгоритму Дейкстри з бінарною купою на графі з V вершинами та E ребрами?

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

Які дві речі треба показати, щоб довести, що задача розпізнавання X є NP-повною?

1. AX не має поліноміального алгоритму, і X розв'язна
2. BX належить до NP, і відома NP-повна задача зводиться до X за поліноміальний час
3. CX зводиться до задачі з P, і X належить до NP
4. DX належить до P, і X зводиться до SAT