Diferencia entre revisiones de «Ordenamiento Shell»
Contenido eliminado Contenido añadido
m r2.7.2+) (robot Añadido: is:Skeljaröðun |
|||
Línea 73:
Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de <math>O(n^2)</math> (usando los incrementos de Shell que comienzan con n/2, n el tamaño del vector y se dividen por 2 cada vez), <math>O(n^{3/2})</math> (usando los incrementos de Hibbard de <math>2^k -1</math>), <math>O(n^{4/3})</math> (usando los incrementos de Sedgewick de <math>9(4^i) - 9(2^i) + 1</math>, o <math>4^{i+1} + 3(2^i) + 1</math>), o <math>O(n\log^2 n)</math>, y posiblemente mejores tiempos de ejecución no comprobados. La existencia de una implementación <math>O(n \log n)</math> en el peor caso del Shell sort permanece como una pregunta por resolver.
NOTA: Los incrementos de Sedgewick se calculan intercalando los valores de las siguientes funciones:
<math>f(i) = 9(4^i) - 9(2^i) +1; f(1)=1, f(2)=9, f(3)=109, f(4)=505, ...) </math>
<math>g(i) = (2^{i+2}) * (2^{i+2} - 3) +1; g(1)=5, g(2)=41, g(3)=209, g(4)=929, ...) </math>
== Referencias ==
| |||