Рубрики

Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 6

Алгоритмы Задачи

Время выполнения алгоритма представлено следующим рекуррентным соотношением:

    if  n <= 3  then   T(n) = n
    else T(n) = T(n/3) + cn

Что из следующего представляет временную сложность алгоритма?
(А) (П)
(В) (n log n)
(С) (П ^ 2)
(D) (n ^ 2log n)
(А) А
(Б) Б
(С) С
(D) D

Ответ: (А)
Объяснение:

T(n) = cn + T(n/3)
     = cn + cn/3 + T(n/9)
     = cn + cn/3 + cn/9 + T(n/27)
Taking the sum of infinite GP series. The value of T(n) will
be less than this sum.
T(n) <= cn(1/(1-1/3))
     <= 3cn/2

or we can say 
cn <= T(n) <= 3cn/2
Therefore T(n) = (n)

Это также может быть решено с помощью основной теоремы для решения повторений. Данное выражение лежит в случае 3 теоремы.
Тест на этот вопрос

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

Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 6

0.00 (0%) 0 votes