¿Complejidad del tiempo para Shell sort?

Question

En primer lugar, aquí está mi código de la ordenación Shell (con Java):

public char[] shellSort(char[] chars) { 
    int n = chars.length; 
    int increment = n/2; 
    while(increment > 0) { 
     int last = increment; 
     while(last < n) { 
      int current = last - increment; 
      while(current >= 0) { 
       if(chars[current] > chars[current + increment]) { 
        //swap 
        char tmp = chars[current]; 
        chars[current] = chars[current + increment]; 
        chars[current + increment] = tmp; 
        current -= increment; 
       } 
       else { break; } 
      } 
      last++; 
     } 
     increment /= 2; 
    } 
    return chars; 
} 

¿Es esta una correcta ejecución de la ordenación Shell (olvidando por el momento acerca de la secuencia brecha más eficiente - por ejemplo, 1,3,7,21. ..)? Lo pregunto porque he oído que la complejidad de tiempo del mejor de los casos para Shell Sort es O (n). (Ver http://en.wikipedia.org/wiki/Sorting_algorithm). No puedo ver este nivel de eficiencia siendo realizado por mi código. Si agregué heurística a él, entonces sí, pero tal como está, no.

Dicho esto, mi principal pregunta ahora - Tengo dificultades para calcular la complejidad del tiempo Big O para mi implementación de ordenamiento de Shell. Identifiqué que el bucle externo como O (log n), el bucle medio como O (n) y el bucle más interno también como O (n), pero me doy cuenta de que los dos bucles internos en realidad no serían O (n) - serían mucho menos que esto - ¿qué deberían ser? Porque obviamente este algoritmo se ejecuta mucho más eficientemente que O ((log n) n^2).

¡Cualquier orientación es muy apreciada ya que estoy muy perdido! : P

Answer 1

El peor de los casos de su implementación es Θ (n^2) y el mejor de los casos es O (nlogn), que es razonable para shell-sort.

El mejor caso ε O (nlogn):

El mejor de los casos es cuando la matriz ya está ordenada. Esto significaría que la instrucción if interna nunca será verdadera, haciendo que el ciclo while interno sea una operación de tiempo constante. El uso de los límites que ha utilizado para los otros bucles da O (nlogn). El mejor caso de O (n) se alcanza al usar un número constante de incrementos.

El peor de los casos ε O (n^2):

Dada su límite superior para cada bucle se obtiene O ((log n) n^2) para el peor de los casos. Pero agregue otra variable para el tamaño de la brecha g. El número de comparar/intercambios necesarios en el interior es ahora < = n/g. El número de comparación/intercambios del medio es < = n^2/g. Agregue el límite superior del número de comparar/intercambiar para cada espacio juntos: n^2 + n^2/2 + n^2/4 + ... < = 2n^2 ε O (n^2). Esto coincide con la complejidad del peor caso conocido para las lagunas que ha utilizado.

El peor caso ε Ω (n^2):

en cuenta la matriz en donde todos los elementos incluso posicionado son mayores que la mediana. Los elementos pares e impares no se comparan hasta que alcanzamos el último incremento de 1. El número de comparaciones/intercambios necesarios para la última iteración es Ω (n^2).