Analyse des algorithmes (complexité)

Question

Comment les algorithmes sont-ils analysés? Qu'est-ce qui fait que quicksort a une performance O(n^2) dans le pire des cas alors que le tri par fusion a une performance O(n log(n)) dans le pire des cas?

Answer 1

C'est un sujet pour tout un semestre. En fin de compte, nous parlons de la limite supérieure du nombre d'opérations qui doivent être terminées avant que l'algorithme se termine en fonction de la taille de l'entrée. Nous n'incluons pas les coefficients (ie 10N vs 4N^2) car pour N assez grand, cela n'a plus d'importance.

Comment prouver ce qu'est le big-oh d'un algorithme peut être assez difficile. Cela nécessite une preuve formelle et il y a beaucoup de techniques. Souvent, un bon moyen ad hoc est de simplement compter combien de passes sur les données de l'algorithme. Par exemple, si votre algorithme est imbriqué pour des boucles, alors pour N éléments, vous devez opérer N fois. Ce serait généralement O (N^2). Pour fusionner le tri, vous divisez les données de moitié à plusieurs reprises. Cela prend log2 (n). Et pour chaque division, vous faites un passage sur les données, ce qui donne N log (n).

Le tri rapide est un peu plus délicat car, dans le cas moyen, il s'agit également de n log (n). Vous devez imaginer ce qui se passe si votre partition divise les données de telle sorte que chaque fois que vous obtenez un seul élément d'un côté de la partition. Ensuite, vous aurez besoin de diviser les données n fois au lieu de log (n) fois ce qui le rend N^2. L'avantage de quicksort est qu'il peut être fait en place, et que nous nous rapprochons habituellement des performances de N log (n).

Answer 2

Les deux quicksort et merge sort divisent le tableau en deux, trient chaque partie récursivement, puis combinent le résultat. Quicksort se sépare en choisissant un élément "pivot" et en partitionnant le tableau en plus petit ou plus grand que le pivot. Fusionner le tri de manière arbitraire, puis fusionner les résultats en temps linéaire. Dans les deux cas, une seule étape est O (n), et si la taille du tableau est divisée par deux, cela donnerait un nombre de pas logarithmique. Nous attendrions donc O (n log (n)).

Cependant, le tri rapide a le pire des cas où la division est toujours inégale, donc vous n'obtenez pas un nombre de pas proportionnel au logarithmique de n, mais un nombre de pas proportionnel à n. Fusionner le tri se divise exactement en deux moitiés (ou le plus près possible) afin qu'il n'a pas ce problème.

Answer 3

• tri rapide a de nombreuses variantes en fonction de sélection de pivot
• Supposons que nous choisissons toujours 1er élément du tableau comme un pivot

Si le tableau d'entrée est triée puis tri rapide sera seulement genre de tri de sélection! Parce que vous ne divisez pas vraiment le tableau .. vous ne choisissez que le premier élément dans chaque cycle

D'un autre côté, le tri par fusion divisera toujours le tableau d'entrée de la même manière, quel que soit son contenu!

A noter également: les meilleures performances en division et en conquête lorsque les divisions sont sensiblement égales!

Answer 4

1. Ceci est une analyse préliminaire des matériaux de cours d'algorithmes.

2. Une opération est définie (c'est-à-dire une multiplication) et l'analyse est effectuée en termes d'espace ou de temps.

3. Cette opération est comptabilisée en termes d'espace ou de temps.Généralement, les analyses sont effectuées en tant que variable dépendante de la taille d'entrée.

Exemple pseudocode:

foreach $elem in @list 

    op(); 

endfor 

Il y aura n opérations effectuées, où n est la taille de @list. Comptez-le vous-même si vous ne me croyez pas.

Pour analyser quicksort et mergesort nécessite un niveau décent de ce qui est connu comme la sophistication mathématique. Lâche, vous résolvez une équation différentielle discrète dérivée de la relation récursive.