Autor Tema: Eficiencia de un método de ordenamiento

0 Usuarios y 1 Visitante están viendo este tema.

01 Septiembre, 2008, 02:23 pm
Leído 1557 veces

Abeja

  • $$\Large \color{red}\pi$$
  • Mensajes: 13
  • Karma: +0/-0
  • Sexo: Femenino
  Hola

  Qué significa que la eficiencia de un método de ordenamiento sea de \( \mathcal O(n^2) \) ? Método de inserción por ejemplo.

  Ojalá alguien se maneje en el tema para que me ayude.  :'(

01 Septiembre, 2008, 03:33 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,539
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

 Quiere decir que el tiempo \( T(n) \) que se tarda en ordenar \( n \) datos con ese algoritmo es:

 existen constantes \( c>0 \) y \( n_0 \) tales que \( T(n)\leq cn^2 \) para \( n\geq n_0 \)

 De manera intutiva estamos diciendo que si multiplicamos por \( k \) el volumen de datos, el tiempo de ordenación de multiplica por \( k^2 \). Eso nos da una idea de la velocidad del algoritmo y de como se "lentifica" al aumentar el volumen de datos.

 Puedes leer una introducción aquí:

http://web.jet.es/jqc/progii2.html

 y algo más formal aquí:

http://decsai.ugr.es/~jhg/TA/PresentacionEficiencia.pdf

Saludos.