Quelles sont les caractéristiques d'un algorithme de complexité temporelle

Parfois, il est facile d'identifier la complexité temporelle d'un algorithme en l'examinant attentivement. Les algorithmes avec deux boucles imbriquées de sont évidemment . Les algorithmes qui explorent toutes les combinaisons possibles de groupes de deux valeurs sont évidemment .N 2 N 2 $N$$N^2$$N$$2^N$

Cependant, je ne sais pas comment "repérer" un algorithme avec une complexité . Une implémentation récursive de fusion, par exemple, en est une. Quelles sont les caractéristiques communes du mergesort ou d'autres algorithmes qui me donneraient un indice si j'en analysais un?Θ ( N log N $\Theta(N \log N)$$\Theta(N \log N)$

Je suis sûr qu'il existe plus d'une façon dont un algorithme peut être de complexité , donc toutes les réponses sont appréciées. BTW Je cherche des caractéristiques générales et des conseils, pas des preuves rigoureuses.$\Theta(N \log N)$

Votre archétype est un algorithme de division et de conquête , qui divise (et recombine) le travail en temps linéaire et se reproduit sur les pièces. Le tri par fusion fonctionne de cette façon: passez O ( n ) temps à diviser l'entrée en deux morceaux à peu près égaux, triez récursivement chaque morceau et passez Θ ( n ) temps à combiner les deux moitiés triées.$\Theta(n \log n)$$O(n)$$\Theta(n)$

Intuitivement, poursuivant l'idée de diviser pour mieux régner, chaque étape de division prend un temps linéaire au total, car l'augmentation du nombre de pièces à diviser correspond exactement à la diminution de la taille des pièces, car le temps pris par la division est linéaire. Le temps de fonctionnement total est le produit du coût total d'une étape de division multiplié par le nombre d'étapes de division. Étant donné que la taille des pièces est divisée par deux à chaque fois, il existe étapes de division log 2 ( n ) , de sorte que le temps de fonctionnement total est n ⋅ log ( n ) . (Jusqu'à une constante multiplicative, la base du logarithme n'est pas pertinente.)$\log_2(n)$$n \cdot \log(n)$

En le mettant dans les équations (), une façon d'estimer le temps d'exécution d'un tel algorithme est de l'exprimer récursivement: T ( n ) = 2 T ( n / 2 ) + Θ ( n ) . Il est clair que cet algorithme prend plus que du temps linéaire, et nous pouvons voir combien plus en divisant par n : T ( n $T(n)$$T(n) = 2 T(n/2) + \Theta(n)$$n$

Ceci est une instance d'un modèle plus général: le théorème maître . Pour tout algorithme récursif qui divise son entrée de taille dans des morceaux de taille et prend un temps pour effectuer la division et de recombinaison, le temps d' exécution satisfait . Cela conduit à une forme fermée qui dépend des valeurs de et et de la forme de . Si et , le théorème maître déclare que .a n / b f ( n ) T ( n ) = a ⋅ T ( n / b ) + f ( n ) a b f a = b f ( n ) = Θ ( n ) T ( n ) = Θ ( n log n $n$$a$$n/b$$f(n)$$T(n) = a \cdot T(n/b) + f(n)$$a$$b$$f$$a = b$$f(n) = \Theta(n)$$T(n) = \Theta(n \log n)$

Deux autres catégories d'algorithmes qui prennent du temps :$\Theta(n \log n)$

Algorithmes où chaque élément est traité tour à tour, et il faut du temps logarithmique pour traiter chaque élément (par exemple HeapSort ou de nombreux algorithmes de géométrie de calcul de balayage plan).

Algorithmes où le temps d'exécution est dominé par une étape de prétraitement de tri. (Par exemple, dans l'algorithme de Kruskal pour un arbre couvrant minimum, nous pouvons trier les bords par poids comme première étape).

Autre catégorie: les algorithmes dans lesquels la sortie a la taille , et donc le temps d'exécution Θ ( n log n ) est linéaire dans la taille de la sortie .$\Theta(n \log n)$$\Theta(n \log n)$

Bien que les détails de ces algorithmes utilisent souvent des techniques de division et de conquête, ils ne doivent pas nécessairement le faire. Le temps d'exécution vient fondamentalement de la question posée, et je pense donc qu'il vaut la peine d'être mentionné séparément.

Cela apparaît dans les structures de données qui sont basées sur un arbre de recherche binaire augmenté, où chaque nœud stocke une structure de données de taille linéaire pour rechercher sur les feuilles dans le sous-arbre de ce nœud. De telles structures de données apparaissent souvent dans la recherche par plage géométrique et sont souvent basées sur un schéma de décomposition . Voir le sondage d'Agarwal .

Pour un exemple concret, considérons l' arborescence , conçue pour répondre aux requêtes de plages orthogonales bidimensionnelles. Bien que l'espace ait ensuite été réduit à l'aide de certaines techniques de compression pour regrouper plusieurs objets en un seul mot, la version de manuel (et la plus intuitive) de la structure de données nécessite un espace (chaque feuille est stockée dans une structure auxiliaire à chaque nœud sur le chemin de la feuille à la racine, ou en O ( log n ) ), et l'algorithme de construction prend du temps linéaire dans l'espace requis .$O(n \log n)$$O(\log n)$

Une complexité de provient des algorithmes de division et de conquête qui divisent leur entrée en k morceaux de taille à peu près égale dans le temps O ( n ) , opèrent sur ces morceaux de manière récursive, puis les combinent dans le temps O ( n ) . Si vous n'opérez que sur certaines pièces, le temps d'exécution passe à O ( n ) .$O(n\log n)$$k$$O(n)$$O(n)$$O(n)$

Ce sont généralement des algorithmes de la variété "diviser pour mieux régner", où le coût de la division et de la combinaison des sous-solutions n'est pas "trop ​​important". Jetez un œil à cette FAQ pour voir quels types de récidives provoquent ce comportement.

En règle générale, les algorithmes de division et de conquête généreront une complexité O (N log N).

$O(n \log n)$

for (i = 0; i < constant; i++){
    for(j = 0; j < n; j++){
        // Do some O(1) stuff on the input
    }
}

// Alternative Variant:
for (i = 0; i < constant; i++){
    for(j = n; j < constant; j++){
        // Do some O(1) stuff on the input
    }
}

$O(n^2)$

Je ne peux pas donner un exemple concret d'un algorithme qui utilise cette boucle, mais il revient souvent lors du codage d'algorithmes personnalisés.