AEDs III 21/03/2011

// Foram colocados alguns exemplos de uso de como funciona a ordem de complexidade com o O(f(x))

Relembrando as definições:
O(f(x)) é algo que está garantidamente menor do que f(x)*c para valores muito muito grandes de x, sendo c uma constante arbitrariamente grande.

<ohm>(f(x)) é algo que está garantidamente maior do que f(x)*d para valores muito muito grandes de x, sendo d uma constante arbitrariamente pequena.

<teta> ou <0> de f(x) é algo que é O(f(x)) e <ohm>(f(x)) ao mesmo tempo. Significando que isso é menor que f(x)*c mas maior que f(x)*d. Segundo as definições de c e d acima.

CONCEITO:

Teorema Mestre de resolução de equações recursivas:

Toda equação recursiva em que se aplica esse teorema deve enquadrar-se no seguinte modelo:

T(n) = A T(n/b) + f(n)
-> sendo: "a>=1"
          "b >1"

A resolução de cada uma dessas equações recursivas se divide em 3 casos, com 3 diferentes meios de resolução:

caso 1: Quando " f(n) = O(n;log(b,a-e);;) "  a solução fica:  "  T(n) = <0>(n;log(b,a);;)  "

caso 2: Quando " f(n) = <0>(n;log(b,a)*log(n);;) "  a solução fica:  "  T(n) = <0>(n;log(b,a)*log(n);;)  "

caso 3: Quando " f(n) = <ohm>(n;log(b,a+e);;) "  a solução fica:  "  T(n) = <0>(f(n))  "
<alfa> f(n/y) <= c*f(n) para n grande.
// Essa linha acima não sei bem o que significa mas tava escrito logo abaixo do caso 3, e copiei rapidamente no fimzinho da aula.