SoloCodigo
Programación General => C/C++ => Mensaje iniciado por: excellion en Miércoles 25 de Febrero de 2004, 19:21
-
La complejidad en el shell sort es n^3/2 en el peor de los casos...pero:
Cuando aplico la distancia uno para hacer la ultima ordenacion me da un vector practicamente ordenado. Aqui tengo q aplicar el metodo de insercion , el cual en el peor de los casos me daria una complejidad de n^2 y en mejor de los casos n, que querría decir que la secuencia estaría ordenada.
Entonces n^3/2, es la complejidad media que tiene el algoritmo??.
Mis argumentos son buenos?.
Gracias.
-
Hola.
Parece que el cálculo del coste en el caso medio de la ordenación por Shell no es tarea sencilla. Aqui te dejo un estracto de un libro:
Se cree que el tiempo de ejecución del caso promedio de la ordenación de Shell, usando incrementos de Hibbard, es O(n^(5/2)), con base en simulaciones, pero nadie ha podido demostrarlo. Pratt demostró que la cota O(n^(3/2)) se aplica a un amplio conjunto de secuencias de incrementos.
Del caso promedio no tengo más, sólo del caso peor. Prueba a buscar por Pratt y Shell Sort en google.
Un saludo.
Ruben3d
-
Perdona, me e equivocado. Quería decir si la complejidad total es n^3/2 porque 3/2 es la mitad entre n^2 y n.
Te hice mal la pregunta.
Un saludo.