Рубрики

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

В соревновании наблюдаются четыре разные функции. Все функции используют один цикл for, и в цикле for выполняется один и тот же набор операторов. Рассмотрим следующее для циклов:

A) for(i = 0; i < n; i++)

  

B) for(i = 0; i < n; i += 2)

  

C) for(i = 1; i < n; i *= 2)

  

D) for(i = n; i > -1; i /= 2)

Если n — размер входных данных (положительный), какая функция наиболее эффективна (если задача, которая должна быть выполнена, не является проблемой)?
(А) А
(Б) Б
(С) С
(D) D

Ответ: (с)
Объяснение: Сложность по времени первого цикла for равна O (n).
Временная сложность секунды для цикла составляет O (n / 2), что эквивалентно O (n) в асимптотическом анализе.
Временная сложность третьего цикла for составляет O (logn).
Четвертый цикл for не заканчивается.
Тест на этот вопрос

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

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

0.00 (0%) 0 votes