Comment calculer l'ordre (grand O) pour des algorithmes plus complexes (par exemple quicksort)

Le logarithme est l'opération inverse de l'exponentiation. Un exemple de l'exponentiation est lorsque l'on double le nombre d'éléments à chaque étape. Ainsi, une échelle logarithmique de l'algorithme de souvent de moitié le nombre d'éléments à chaque étape. Par exemple, la recherche binaire tombe dans cette catégorie.

De nombreux algorithmes nécessitent un nombre logarithmique de grands pas, mais à chaque grande étape nécessite O(n) unités de travail. Mergesort tombe dans cette catégorie.

Habituellement, vous pouvez identifier ces types de problèmes par la visualisation d'un arbre binaire équilibré. Voici par exemple la fusion de tri:

 6   2    0   4    1   3     7   5
  2 6      0 4      1 3       5 7
    0 2 4 6            1 3 5 7
         0 1 2 3 4 5 6 7

En haut à l'entrée, comme les feuilles de l'arbre. L'algorithme crée un nouveau nœud en triant les deux nœuds au-dessus d'elle. Nous savons que la hauteur d'un arbre binaire équilibré est O(log n) il y a donc O(log n) grandes étapes. Toutefois, la création de chaque nouvelle ligne prend O(n) de travail. O(log n) grandes étapes de O(n) le travail de chacun que mergesort est O(n log n) dans l'ensemble.

Généralement, O(log n) algorithmes de ressembler à la fonction ci-dessous. Ils arrivent à jeter la moitié des données à chaque étape.

def function(data, n):
    if n <= constant:
       return do_simple_case(data, n)
    if some_condition():
       function(data[:n/2], n /2) # Recurse on first half of data
    else:
       function(data[n/2:], n - n /2) # Recurse on second half of data

Tout en O(n log n) algorithmes de ressembler à la fonction ci-dessous. Ils séparent les données dans la moitié, mais ils doivent tenir compte de ces deux moitiés.

def function(data, n):
    if n <= constant:
       return do_simple_case(data, n)
    part1 = function(data[n/2:], n /2)      # Recurse on first half of data
    part2 = function(data[:n/2], n - n /2)  # Recurse on second half of data
    return combine(part1, part2)

Où do_simple_case() prend O(1) fois et de les combiner() ne prend pas plus de O(n) fois.

Les algorithmes n'ont pas besoin de diviser les données exactement de moitié. Ils pourraient diviser en un tiers et deux tiers, et que ce serait bien. Pour le cas moyen de la performance, de la scission en deux en moyenne est suffisante (comme QuickSort). Tant que la récursivité est fait sur des morceaux de (n/quelque chose) et (n - n/quelque chose), c'est correct. Si c'est le brisant en (k) et (n-k), alors la hauteur de l'arbre sera en O(n) et pas de O(log n).

Pour certains algorithmes, l'obtention d'un serré en partance pour le temps d'exécution par le biais de l'intuition est presque impossible (je ne pense pas que je vais jamais être capable de deviner un O(n log log n) temps d'exécution, par exemple, et je doute que quelqu'un pourra jamais attendre de vous que vous). Si vous pouvez obtenir vos mains sur le CLRS Introduction aux Algorithmes de texte, vous trouverez un joli traitement approfondi de notation asymptotique qui est appropriée rigoureux sans être complètement opaque.

Si l'algorithme est récursif, un moyen simple de tirer un encadrement est d'écrire une récidive et pour le résoudre, soit de manière itérative ou à l'aide de la Maître Théorème ou d'une autre façon. Par exemple, si vous ne cherchez pas à être super rigoureux à ce sujet, la meilleure façon d'obtenir QuickSort est temps d'exécution est à travers le Maître Théorème -- QuickSort implique de partitionnement de la matrice en deux relativement égale des sous-tableaux (il devrait être assez intuitif de voir que c'est O(n)), et puis l'appel de QuickSort de manière récursive sur ces deux sous-tableaux. Ensuite, si nous les laissons T(n) désigner le temps d'exécution, nous avons T(n) = 2T(n/2) + O(n), qui, par le Maître de la Méthode est O(n log n).

Je vais tenter de faire une analyse intuitive de pourquoi Mergesort est n log n, et si vous pouvez me donner un exemple de n log log n de l'algorithme, je peux travailler à travers elle aussi.

Mergesort est un exemple de tri qui fonctionne par le partage d'une liste d'éléments à plusieurs reprises jusqu'à ce que seuls les éléments et la combinaison de ces listes ensemble. Le fonctionnement principal dans chacun de ces fusions est la comparaison et chaque fusion nécessite tout au plus n comparaisons où n est la longueur des deux listes combinées. À partir de ce que vous pouvez tirer de la récidive et de résoudre facilement, mais nous allons éviter cette méthode.

Plutôt de considérer comment Mergesort va se comporter, nous allons faire une liste et de le diviser, puis prendre les moitiés et de diviser à nouveau, jusqu'à ce que nous avons n partitions de longueur 1. J'espère qu'il est facile de voir que cette récursivité ne vont log (n) de profondeur jusqu'à ce que nous avons divisé la liste dans notre n partitions.

Maintenant que nous avons que chacun de ces n partitions doivent être fusionnées, puis une fois ceux-ci sont regroupées au niveau suivant devront être fusionnés, jusqu'à ce que nous avons une liste de longueur n de nouveau. Reportez-vous à la page wikipedia graphique pour un exemple simple de ce processus http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg.

Maintenant tenir compte de la quantité de temps que prendra ce processus, nous allons avoir log (n) les niveaux et à chaque niveau, nous aurons à la fusion de toutes les listes. Il s'avère que chaque niveau prendra n le temps de fusion, parce que nous allons la fusion d'un total de n éléments à chaque fois. Ensuite, vous pouvez assez facilement voir qu'il va prendre la n log (n) le temps de trier un tableau avec mergesort si vous prenez l'opération de comparaison pour être l'opération la plus importante.

Si quelque chose n'est pas clair ou j'ai sauté quelque part s'il vous plaît laissez-moi savoir et je peux essayer d'être plus verbeux.

Modifier La Seconde Explication:

Laissez-moi réfléchir, si je peux vous expliquer cela mieux.

Le problème est décomposé en un tas de petites listes et puis les petites listes sont triées et regroupées jusqu'à ce que vous revenir à la liste originale qui est maintenant triée.

Lorsque vous cassez les problèmes que vous avez plusieurs niveaux de la taille d'abord vous allez avoir deux listes de taille: n/2, n/2, alors au prochain niveau, vous aurez quatre listes de taille: n/4, n/4, n/4, n/4, au niveau suivant, vous devrez n/8, n/8 ,n/8 ,n/8, n/8, n/8 ,n/8 ,n/8 cela continue jusqu'à n/2^k est égal à 1 (chaque subdivision est la longueur divisée par une puissance de 2, et non pas toutes les longueurs sera divisible par quatre, alors il ne sera pas tout à fait cette jolie). Cela est répété à la division par deux et peuvent continuer à la plupart des log_2(n) fois, parce que 2^(log_2(n) )=n, donc plus de division par 2 devrait permettre d'obtenir une liste de taille zéro.

Maintenant, la chose importante à noter est qu'à chaque niveau on a n d'éléments pour chaque niveau de la fusion prendra n le temps, parce que la fusion est une opération linéaire. Si il y a log(n), les niveaux de la récursivité ensuite, nous allons effectuer cette opération linéaire log(n) fois, par conséquent, notre temps de course sera n log(n).

Désolé si ce n'est pas très utile.