22/09/2019, 03:19:58 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: LISTADO ACTUALIZADO DE CURSOS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Complejidad de algoritmos  (Leído 591 veces)
0 Usuarios y 1 Visitante están viendo este tema.
busterxd
Pleno
****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Colombia Colombia

Mensajes: 113


Ver Perfil
« : 07/05/2010, 10:09:35 pm »

Hola tengo problemas para demostrar este teorema sobre complejidad de algoritmos:

Sean [texx]f,g:\mathbb{N}\rightarrow{\mathbb{R^+}}[/texx] y considere:
[texx]c=\displaystyle\lim_{n \to{+}\infty}{\displaystyle\frac{f(n)}{g(n)}}[/texx]

Probar que:

a)si c=0 o finito [texx]\rightarrow{f(n)\in{O(g(n))}}[/texx]
b)si c=0 [texx]\rightarrow{f(n)\in{o(g(n))}}[/texx]
c)si [texx]c=+\infty\rightarrow{f(n)\in{w(g(n))}}[/texx]
aver si me ayudan porfavor ya lo intente y ni idea
En línea
topo23
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Argentina Argentina

Mensajes: 940


Ver Perfil
« Respuesta #1 : 08/05/2010, 12:50:55 am »

Todos los items se pueden demostrar trivialmente usando la definicion de limite.

Por ejemplo b) por definicion de limite para todo [texx]\epsilon>0[/texx] existe [texx]n_0[/texx] tal que [texx]n > n_0[/texx] implica que [texx]\left|\frac{f(n)}{g(n)}\right|<\epsilon[/texx], o sea [texx]|f(n)| < \epsilon|g(n)|[/texx], que es la definicion de o.

En línea

.
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!