Type d'insertion dans le cas le plus défavorable

-1

Pourquoi dans le pire des cas le temps d'exécution du type d'insertion est-il n (n-1)/2 ~ n^2? mettant en évidence la division de 2?Type d'insertion dans le cas le plus défavorable

Source

2012-06-23 user1475421

Le temps d'exécution n'est pas n(n-1)/2, chaque étape nécessite plus de 1 la machine OP (dans toutes les machines, je suis au courant). C'est pourquoi nous habituellement utiliser big O notation et "ignorer" constantes dans les algorithmes analyse - nous voulons rendre notre analyse générique et la plate-forme indépendante.
Le tri par insertion est analysé comme n(n-1)/2 = O(n^2) car il s'agit de sum of arithmetic progression. La première itération nécessite 1 étape, la deuxième 2 étapes, .. la nième nécessite n étapes, donc nous obtenons 1 + 2 + ... + n = n(n-1)/2 de la somme de la progression arithmétique.

Source

2012-06-23 08:17:47 amit

Je comprends la partie de progression arithmétique, mais je ne comprends pas où la division par 2 s'inscrit? – user1475421

@ user1475421 la première itération itérative est 1 étape, la 2ème est 2 étapes, la 3rs est 3 étapes, ... le nième est n étapes, vous donnant total de '1 + 2 + 3 + ... + n' étapes , qui somme à 'n (n-1)/2'. Demandez-vous pourquoi "1 + 2 + ... + n' somme" n (n-1)/2'? – amit

Je comprends n (n-1) partie mais ne peux pas comprendre où la partie/2 s'inscrit? – user1475421

Introduction aux algorithmes donne les détails du tri par insertion dans le chapitre 2.1, qui traitent tout le processus de tri par insertion.

Le pire des cas est causé par le commutateur du sous-réseau dans l'ordre inverse.

Source

2012-06-23 13:21:19

Donc, j'ai pris le temps de lire le chapitre que vous avez suggéré .. Je suis même allé jusqu'à l'acheter. Vaut vraiment le coup. Ne pas mettre un négatif sur ce chapitre ne précise pas pourquoi la progression arithmétique est divisée par 2? – user1475421

C'est juste un résultat simple de la somme de la progression arithmétique qui est célèbre quand Gauss l'a résolu comme un enfant. –

Nous pouvons déduire l'expression comme ceci: additionner le premier et le dernier en tant que paire, puis sumer le second et le dernier mais un comme une paire, etc. Il est clair que toute la somme des paires est égale. Définissez la somme en tant que s1. Donc, pour obtenir la somme originale, nous pouvons répéter n fois s1 et diviser par 2, car nous répétons la somme originale une fois de plus. –

Je sais que cela a été fermé pour toujours, mais je voulais ajouter cela pour quelqu'un d'autre qui essaie de rafraîchir les mathématiques derrière le cas le plus défavorable. J'ai trouvé un grand video qui a expliqué le n (n-1)/2 formule ainsi:

Pour évaluer la somme de:

enter image description here

Vous devez d'abord déposer dans la notation de la série (appeler s):

s = 1 + 2 + 3 + ... n-3+n-2+n-1

montrent ensuite dans le sens inverse:

s = n-1+n-2+n-3+ ... 3 + 2 + 1

Ajouter s à s ensemble en ajoutant chaque paire et vous obtenez: n+n+n+....n+n+n

Ou en d'autres termes 2s = n(n-1) parce que vous avez n, n-1 fois et il vous a fallu deux de ces ensembles pour l'obtenir.

Alors vous avez juste besoin de résoudre l'inégalité 2s = n(n-1) qui vient à s = n(n-1)/2.

Source

2014-09-20 21:46:54 DanK

Type d'insertion dans le cas le plus défavorable

Répondre

Questions connexes