Рекуррентное соотношение с заданными T (0) и T (n) - Big O - PullRequest
Новая
       83

Рекуррентное соотношение с заданными T (0) и T (n) - Big O

0 голосов
/ 22 января 2019

Так что мне нужно решить эти два повторения: 

a) T(0)=1   T(n)=3T(n-1)+1 

b) T(1)=1 T(n)=4T(n/4)+1

И я довольно застрял, я даже не знаю, как начать это, и, ища ответ, я не понимал, как сделать это шаг за шагом.

Я пытаюсь понять это прямо сейчас, поэтому, если никто не ответит, я постараюсь изложить здесь, как я думаю, что это сделано.

1 Ответ

0 голосов
/ 22 января 2019

Хорошо, я думаю, что я понял это благодаря видео на yt.

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

для а) 

T(0)=1  T(n)=3T(n-1)+1
We make two columns
Solution                              Work
k=1 T(n)=3T(n-1)+1                    T(n-1)=3T(n-2)+1
    T(n)=3[3T(n-2)+1]+1               
k=2     =3^2T(n-2)+2                  T(n-2)=3T(n-3)+1
        =3^2[3T(n-3)+1]+2
k=3     =3^3T(n-3)+3

//Now we see that there's a pattern here so we just have to write it down

n=k     T(n)=3^kT(n-k)+k              T(n)=3^nT(0)+n
                                      T(n)=3^nT*1+n
                                      T(n)=3^n+n ~ O(3^n)

для б) 

T(1)=1  T(n)=4T(n/4)+1
We make two columns
Solution                              Work  
k=1 T(n)=4T(n/4)+1                    n=4^m
        =4T(4^m-1)+1                  T(m-1)=4T(4^m-2)+1
        =4[4T(4^m-2)+1]+1
k=2     =4^2T(4^m-2)+2                T(m-2)=4T(4^m-3)+1
        =4^2[4T(4^m-3)+1]+2
k=3     =4^3T(4^m-3)+3                

//same pattern thing over here

n=k     =4^kT(4^m-k)+k                k=log4(n)
                                      T(m)=4^kT(1)+k
                                      T(n)=4^log4(n)*1+log4(n) ~ O(log4(n))
...