Le temps de la complexité de tri de Shell?
Tout d'abord, voici mon tri de Shell code (en 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;
}
Est-ce une mise en œuvre correcte de tri de Shell (en oubliant pour l'instant sur le plus efficace de l'écart de la séquence par exemple, 1,3,7,21...)? Je demande parce que j'ai entendu dire que le meilleur des cas, le temps de la complexité de Tri de Shell est O(n). (Voir http://en.wikipedia.org/wiki/Sorting_algorithm). Je ne vois pas ce niveau d'efficacité réalisés par mon code. Si j'ai ajouté de l'heuristique, alors ouais, mais comme il est, pas.
Cela étant dit, ma question principale, maintenant je vais avoir de la difficulté à calculer le Big O moment de la complexité pour mon tri de Shell de mise en œuvre. J'ai identifié que les extérieurs de la boucle que O(log n), le milieu de la boucle que O(n), et le plus intérieur de la boucle aussi que O(n), mais je me rends compte à l'intérieur de deux boucles, ne serait O(n) - ils seraient beaucoup moins que ce que devraient-ils être? Car il est évident que cet algorithme fonctionne beaucoup plus efficacement que O((log n) n^2).
De toute orientation est apprécié, comme je suis très perdu! 😛
OriginalL'auteur Matt Larsen | 2012-10-07
Vous devez vous connecter pour publier un commentaire.
Le pire des cas de la mise en œuvre est en Θ(n^2) et le meilleur des cas est en O(nlogn) qui est raisonnable pour shell-tri.
Le meilleur des cas ∊ O(nlogn):
Le meilleur des cas, c'est quand le tableau est déjà trié. L'signifierait que l'intérieur si l'instruction ne sera jamais vraie, prise de l'intérieur tandis que la boucle d'une constante de temps de l'opération. En utilisant les limites que vous avez utilisés pour les autres boucles donne O(nlogn). Le meilleur des cas en O(n) est atteint en utilisant un nombre constant de incréments.
Le pire des cas ∊ O(n^2):
Donné votre limite supérieure pour chaque boucle, vous obtenez O((log n)n^2) pour le pire-cas. Mais ajouter une autre variable de la taille de l'espace g. Le nombre de comparaison/échanges nécessaires à l'intérieur, tout est maintenant <= n/g. Le nombre de comparaison/échanges du milieu tout en <= n^2/g. Ajouter de la valeur limite supérieure du nombre de comparaison/échanges pour chaque écart ensemble: n^2 + n^2/2 + n^2/4 + ... <= 2n^2 ∊ O(n^2). Cela correspond à l'connu pire-la complexité de l'affaire pour combler les lacunes que vous avez utilisés.
Le pire des cas ∊ Ω(n^2):
Considérer le tableau où tous les éléments positionnés sont supérieures à la médiane. L'étrange et même des éléments de comparaison jusqu'à ce que nous atteignons le dernier incrément de 1. Le nombre de comparaison/échanges nécessaires pour la dernière itération est Ω(n^2).
ma conférence de matériaux que les plus connues temps d'exécution est O(n^1.5). "connue", parce que l'analyse n'est pas encore achevé à ce jour.
OriginalL'auteur fgb