Время выполнения алгоритма представлено следующим рекуррентным соотношением:
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 теоремы.
Тест на этот вопрос
Рекомендуемые посты:
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 11
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 11
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 9
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 4
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 8
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 1
- Алгоритмы | Анализ алгоритмов (рецидивов) | вопрос 2
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 11
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 3
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 7
- Алгоритмы | Анализ алгоритмов | Вопрос 8
- Алгоритмы | Анализ алгоритмов | Вопрос 1
- Алгоритмы | Анализ алгоритмов | Вопрос 9
- Алгоритмы | Анализ алгоритмов | Вопрос 10
- Алгоритмы | Анализ алгоритмов | Вопрос 15
0.00 (0%) 0 votes