A recursão

7

Eu estou olhando para a recorrência

T(n)=T(n/2)+T(n/3)+n,
que descreve o tempo de execução de algum algoritmo não especificado (casos base não são fornecidos).

Usando indução, descobri que T(n)=O(nlogn), mas foi informado que isso não é justo. De fato, assuma indutivamente queT(k)Cklogk para todos k<n (e valores suficientemente grandes de k), então

T(n)Cn2logn2+Cn3logn3+n=C56nlognn(C/2+Clog3/31).

Agora eu escolho C grande o suficiente para (C/2+Clog3/31)>0e, portanto, a última expressão é dominada por C56nlognCnlogn.

Minha primeira pergunta é: o que é mais restrito que isso?

Segundo, tentei usar o método Akra-Bazzi para resolver isso, então vamos p resolver

(12)p+(13)p=1.
Então aproximadamente p=0.79, e com g(n)=n) Eu recebo
1ng(u)up+1du=1n1updu=11p(n1p1),
e entao

T(n)=Θ(np(1+11p(n1p1))).

Isso é igual a Θ(np+11pn11pnp), de modo geral Θ(n), Desde a p<1. Minha segunda pergunta é que eu realmente não acredito nissoT é linear, então o que deu errado na minha aplicação do Akra-Bazzi?

Cumprimentos.

HowDoICSharply
fonte

Respostas:

5

E se T(1)6 e T(2)12, podemos mostrar que T(n)6n por indução.

T(n)=T(n/2)+T(n/3)+n6(n/2)+6(n/3)+n=6n.

De maneira mais geral, vamos c>6 ser uma constante que T(1)c e T(2)2c, então podemos provar rotineiramente que T(n)cn. Embora possa parecer inacreditável para você, é verdade que

T(n)=O(n).

Intuitivamente, desde 12+13<1, os termos T(n/2) e T(n/3) não é grande o suficiente para levantar n a um poder de n de um expoente maior.

Não há nada de errado em sua aplicação do método Akra-Bazzi, que nos diz que T(n)=Θ(n).

John L.
fonte
4

Deixei S(n)=T(n)/n. EntãoS(n) satisfaz a recorrência

S(n)12S(n2)+13S(n3)+1.
Em particular, se C satisfaz
12C+13C+1C
então S(n/2),S(n/3)C implicaria S(n)C. Este é o caso de todosC6.

Yuval Filmus
fonte