Рубрики

Алгоритмы | Анализ алгоритмов | Вопрос 17

Пусть s будет отсортированным массивом из n целых чисел. Пусть t (n) обозначает время, необходимое для наиболее эффективного алгоритма, чтобы определить, есть ли два элемента с суммой менее 1000 в с. Какие из следующих утверждений верно? (GATE CS 2000)
а) t (n) равно 0 (1)
б) n <t (n) <n
c) n log 2 n <t (n) <
d) t (n) =

(А)
(Б) б
(С) с
(D) d

Ответ: (А)
Объяснение: Пусть массив отсортирован в порядке возрастания, если сумма первых двух элементов меньше 1000, то есть два элемента с суммой меньше 1000, иначе нет. Для сортировки массива в порядке убывания нам нужно проверить последние два элемента. Для структуры данных массива число операций фиксировано в обоих случаях и не зависит от n, сложность равна O (1)
Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | Анализ алгоритмов | Вопрос 17

0.00 (0%) 0 votes