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

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

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

Алгоритм O(n²) работает 1 секунду при n = 1000. Примерно сколько он будет работать при n = 2000?

1. A1 секунду
2. B8 секунд
3. C4 секунды
4. D2 секунды

Что описывает время работы в среднем случае?

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

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

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

Вы один раз сортируете массив из n элементов, а затем отвечаете на k запросов о принадлежности бинарным поиском. Какова общая стоимость?

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

Почему основание логарифма в O большом обычно не указывают, как в O(log n)?

1. AЛогарифмы всегда округляются до целых
2. BЛогарифмы по разным основаниям отличаются лишь постоянным множителем
3. CВсе логарифмы в информатике имеют основание 10, так что оно подразумевается
4. DОснование имеет значение только при малых n

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

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

Каковы затраты времени и памяти при вычислении n-го числа Фибоначчи циклом, хранящим только два последних значения?

1. AO(log n) времени и O(n) памяти
2. BO(2ⁿ) времени и O(1) памяти
3. CO(n) времени и O(1) памяти
4. DO(n) времени и O(n) памяти