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

Какова временная сложность бинарного поиска в отсортированном массиве?

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

Какова временная сложность линейного поиска в неотсортированном массиве из n элементов (в худшем случае)?

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

Какова временна́я сложность поиска наибольшего значения в неотсортированном массиве из n чисел?

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

Какова временна́я сложность умножения двух матриц n × n стандартным тройным циклом?

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

Какое жадное правило в задаче о выборе заявок всегда даёт максимальное число непересекающихся заявок?

1. AВыбрать заявку, которая заканчивается раньше всех, затем повторить с совместимыми
2. BВыбрать заявку, которая начинается раньше всех
3. CСначала выбрать самую короткую заявку
4. DСначала выбрать заявку с наименьшим числом пересечений, затем повторить с совместимыми

Какова амортизированная временная сложность добавления элемента в конец динамического массива, который удваивает свою ёмкость при заполнении?

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

Задача о рюкзаке 0/1, решаемая динамическим программированием, требует O(nW) времени. Почему это называют псевдополиномиальным временем?

1. AПотому что n всегда мало
2. BПотому что он работает только при W = 0
3. CПотому что алгоритм рандомизированный, и время его работы меняется для каждого входа
4. DW — число, поэтому время экспоненциально относительно количества битов, используемых для записи W

Какова амортизированная стоимость инкремента двоичного счётчика, если один инкремент может изменить много битов?

1. AO(n log n) на инкремент
2. BO(log n) на инкремент
3. CO(1) на инкремент
4. DO(n) на инкремент