Алгоритмы и сложность: лист заданий с ответами

Какова временная сложность сортировки слиянием в худшем случае?

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

Как называется рост O(2ⁿ)?

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

Какой алгоритм сортировки выбирает опорный элемент и разбивает массив на меньшие и бо́льшие элементы?

1. AСортировка вставками
2. BСортировка слиянием
3. CСортировка пузырьком
4. DБыстрая сортировка

Примерно сколько сравнений нужно бинарному поиску в худшем случае на отсортированном массиве из 1,000,000 элементов?

1. AОколо 20
2. BОколо 100
3. CОколо 500,000
4. DОколо 1,000

Что вычисляет алгоритм Флойда–Уоршелла и как быстро?

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

Что измеряет амортизационный анализ?

1. AСреднюю стоимость одной операции в худшей последовательности операций
2. BОжидаемую стоимость на случайных входах
3. CСтоимость одной самой дорогой операции в любом месте последовательности
4. DСтоимость алгоритма на лучшем входе

Алгоритм динамического программирования Хелда–Карпа точно решает задачу коммивояжёра. Каково время его работы для n городов?

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

Какое утверждение о P и NP верно?

1. AКаждая задача из P также принадлежит NP
2. BРешения задач NP невозможно быстро проверить
3. CДоказано, что P ≠ NP
4. DNP означает «неполиномиальный» (not polynomial)