Pregunta Cómo obtener Omega (n)


Tengo la fórmula a (n) = n * a (n-1) +1; a (0) = 0

¿Cómo puedo obtener la notación Omega, Theta o O sin el teorema maestro o alguien tiene un buen sitio para entender la explicación?


5
2018-05-03 15:26


origen


Respuestas:


El teorema del Maestro ni siquiera se aplica, por lo que no poder usarlo no es una gran restricción.

Un enfoque que funciona aquí es adivinar límites superiores e inferiores, y luego probar estas conjeturas por inducción si las suposiciones son buenas.

a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 10
a(4) = 41

Una conjetura razonable para un límite inferior es que a (n)> = n! para n> 1. Esto es cierto para n = 1. Supongamos que es verdad para n = k-1.

a(k) = ka(k-1)+1 
     >= k (k-1)! + 1 
     >= k!. 

Entonces, si es verdad para n = k-1, entonces es verdadero para n = k, entonces a (n)> = n! para todos los enteros positivos n, y a (n) = Omega (n!).

Una conjetura razonable para un límite superior está en a (n) <= 2 (n!). Esto es cierto para los primeros valores, pero resulta un poco incómodo probar el uso de la inducción. A veces con pruebas inductivas, es mejor probar algo más fuerte. En este caso, es mejor probar que a (n) <2 (n!), O que a (n) <= 2 (n!) - 1. Esto es cierto para n = 1. Supongamos que es cierto para n = k-1 para algunos k-1> = 1. Entonces

a(k) = k(a(k-1))+1 
    <= k(2(k-1)!-1)+1 
     = 2(k!) +1-k 
    <= 2(k-1)!-1. 

Entonces, para cualquier n> = 1, a (n) <2 (n!). Como tenemos un límite inferior y un límite superior de la forma c * (n!), A (n) = Theta (n!).


5
2018-05-03 16:37



Ya has notado que tu fórmula está muy cerca del factorial. n!. Ahora puede expresar este hallazgo de una manera más formal: puede probar, por ejemplo, que

n! < a(n) < 2*n! (for big enough n)

Si esto es cierto, entonces todos O, Θ y Ω son n!.

Creo que puedes probar la desigualdad anterior, o alguna variante de ella, usando inducción (aunque no lo he probado).


3
2018-05-03 16:16



Insinuación:

Dividiendo a (n) por n !, los primeros términos son

a(1)/1! = 1/1! = 1
a(2)/2! = (2.1+1)/2! = 1 + 1/2!
a(3)/3! = (3.(2.1+1)+1)/3! = 1 + 1/2! + 1/3!
a(4)/4! = (4.(3.(2.1+1)+1)+1)/4!= 1 + 1/2! + 1/3! + 1/4!
...

Esto establece el estrecho horquillado

n! <= a(n) < (e-1).n!

y a(n) es en Θ(n!).


2
2018-05-03 17:13