сложность функции T(N)=T(n/2)+2^n

Я учусь на курсе алгоритмов в университете. Я знаю, как применить несколько рекурсивных методов, чтобы найти эксплуатационные расходы более простых функций, но 2^n в этом вопросе вызывает у меня проблемы. Вот что я пытался применить основную теорему

a=1, b=2 n^log2(1)= n^0.65

Это приводит к n^0=1. Я знаю, что это должно быть полиномиальное число, умноженное на f(N), которое равно 2^n, но я не понимаю, как это можно сравнить с 2^n.

Я пробовал и с деревом рекурсии, но это стало слишком сложно.


algorithm master-theorem
person aneena    schedule 06.03.2015    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Вы можете применить третий случай основной теоремы, описанный здесь потому что f(n) равно Ω(nloga).

Here, 
f(n) = 2^n , and
Ω(n^log 1) = Ω(1)

2^n = Ω(1) , потому что для некоторой константы c>0 и всех достаточно больших n 2^n ≥ c*1.

So T(n) = f(n)
T(n) = O(2^n)

person Nikunj Banka    schedule 06.03.2015
comment
Я ошибся, случай 3 может быть применен. - person Codor; 06.03.2015
comment
не могли бы вы помочь устранить эту путаницу, я читал, что основная теорема может применяться только тогда, когда n ^ loga (b) может быть выражено как n ^ loga (b) + ^ E или n ^ loga (b) - ^ E, где E равно ›0 в противном случае неприменимо. Но я не вижу этого в вашем решении. - person aneena; 06.03.2015
comment
@aneenaЧестно говоря, я не помню ни одного рекуррентного отношения, в котором вступал бы в действие фактор E. Я бы порекомендовал вам попробовать несколько вопросов из pdf-файла, на который я ссылался, и посмотреть, используется ли E где-нибудь. - person Nikunj Banka; 06.03.2015

arrow_upward
2
arrow_downward

Это достаточно легко сделать и без основной теоремы:

T(n) = T(n / 2) + 2^n)
     = T(n / 4) + 2^(n / 2) + 2^n
     = ...
     < 2^0 + 2^1 + ... + 2^n
     = [2^(n + 1) - 1] / (2 - 1) (sum of a geometric progression formula)

=> T(n) = O(2^(n + 1)) = O(2*2^n) = O(2^n)
person IVlad    schedule 06.03.2015
comment
Я не могу решить следующее повторение T (n) = 3T (n/5) + lg ^ 2 n в моей работе: применение основной теоремы a = 3 b = 5 n ^ log5 ^ 3n = n ^ log ^ 0,65 это приводит к n^0=1 это не сравнимо с log^2n Я пробовал и с деревом рекурсии, но получилось слишком сложно. Пожалуйста, помогите - person aneena; 06.03.2015
comment
@aneena - это совсем другой вопрос. Пожалуйста, начните для него другой вопрос и обязательно покажите свою работу, чтобы она не была закрыта. - person IVlad; 06.03.2015