Решение T (n) = 2T (n ^ (1/2)) + 1 асимптотически с использованием дерева рекурсии?

time-complexity big-o recurrence

4649 просмотра

3 ответа

6 Репутация автора

Мне нужно решить повторение

T (n) = 2T (n 1/2 ) + 1

Мне нужно найти асимптотическую сложность времени. Я использую метод дерева рекурсии, но я застреваю. Я знаю, что ответ Θ (войдите n), но я не уверен, как прийти к этому. Как вы решаете это повторение?

Автор: Mahe Источник Размещён: 18.07.2016 05:59

Ответы (3)


1 плюс

0 Репутация автора

Давайте сделаем замену введите описание изображения здесь

затем

введите описание изображения здесь

Где Nколичество терминов до окончания серии.

А что есть N? Это зависит от ответа на комментарий amit . Предположим, что не целочисленные значения допускаются для nin T(n), и это Tзаканчивается (= 0) n < Cдля некоторой константы C > 1.

Тогда нам нужно

! [введите описание изображения здесь

Таким образом, сложность также зависит от C:

введите описание изображения здесь


РЕДАКТИРОВАТЬ: Данные в поддержку моего ответа:

  • график Tпротив log n, C = 1.5:

введите описание изображения здесь

  • график Tпротив - log C, n = 2^64:

введите описание изображения здесь

Как видите, оба линейны.

Автор: user3235832 Размещён: 18.07.2016 08:15

3 плюса

279976 Репутация автора

Если вы видите повторение T (n), в котором один из терминов зависит от квадратного корня от размера ввода, часто полезно определить новое повторение

S (k) = T (2 k )

поскольку с рекуррентным результатом в k часто работать намного проще, чем с соответствующим рекуррентным значением в n. В нашем случае мы имеем

S (k) = T (2 k )

= 2T (√ (2 k )) + 1

= 2T (2 к / 2 ) + 1

= 2S (к / 2) + 1

Обратите внимание, что теперь у нас есть повторение, которое соответствует форме, ожидаемой основной теоремой (и с которой, как правило, работать намного легче, чем с исходной). Мы можем решить это возвращение к S (k) = Θ (k) с помощью ряда различных методов.

Поскольку мы знаем, что S (k) = Θ (k), что мы можем сказать о T (n)? Что ж, предполагая, что у нас все в порядке, выдумывая вещи, которые не являются точными степенями двух, мы можем сказать, что T (n) ≈ S (lg n), поскольку S (lg n) = T (2 lg n ) = T ( п). Поэтому мы получаем, что

T (n) = S (lg n) = Θ (lg n)

поэтому T (n) = Θ (lg n).

Вот еще один способ получить этот результат, который менее математичен и более интуитивен. Представьте форму дерева рекурсии, которое сформировано путем расширения исходной рекурренции T (n). На верхнем уровне у нас есть один вызов размера n, выполняющий 1 работу. На следующем уровне у нас есть два вызова размером 2 √n на общую сумму 2 работы. На нижнем уровне четыре звонка размером 4 √n, всего 4 работы. В целом, на уровне k у нас есть 2 k вызовов, каждый из которых выполняет 2 k √n работы. Рекурсия заканчивается, когда n становится достаточно маленьким (скажем, n = 2), что происходит на некотором уровне k. На этом этапе общая проделанная работа будет

1 + 2 + 4 + 8 + 16 + ... + 2 k = 2 (2 k ) - 1.

Если мы сможем решить для k, мы будем знать, сколько всего работы сделано. Обратите внимание, что рекурсия останавливается, когда входная величина падает до размера 2, что означает, что k, которое мы хотим, это тот, где 2 k √n = 2. Решая для k, мы видим, что

2 k √n = 2

n = 2 2 k

LG LG N = K

В общем, если вы видите, что что-то сокращается из-за фактора квадратного корня, вы должны ожидать, что число итераций до того, как термин уменьшится до константы, равно O (log log n) . Таким образом, общая проделанная работа составляет 2 (2 lg lg n ) + 1 = 2 lg n - 1 = Θ (lg n), как и раньше.

Автор: templatetypedef Размещён: 18.07.2016 08:32

0 плюса

1 Репутация автора

Используя метод дерева рекурсии, вы можете решить следующее: перейдите по этой ссылке

Автор: shubham kumar Размещён: 12.04.2019 11:12
Вопросы из категории :
32x32