Quelle est la complexité temporelle de l'algorithme récursif

La complexité temporelle de l'algorithme récursif est : [T(n)=o(f(n))], ce qui signifie qu'à mesure que la taille du problème n augmente, le taux de croissance du temps d'exécution de l'algorithme et f (n) Le taux de croissance est proportionnel au taux de croissance, appelé complexité temporelle asymptotique de l'algorithme.

Complexité temporelle de l'algorithme récursif

Complexité temporelle :

Généralement, le nombre de répétitions des opérations de base dans l'algorithme est fonction f(n) de la taille du problème n, puis analysez le changement de f(n) avec n et déterminez l'ordre de grandeur de T(n). « o » est utilisé ici pour représenter l'ordre de grandeur et donne la complexité temporelle de l'algorithme.

T(n)=o(f(n));

Cela signifie qu'à mesure que la taille du problème n augmente, le taux de croissance du temps d'exécution de l'algorithme est proportionnel au taux de croissance de f(n) , appelée complexité temporelle asymptotique de l’algorithme. Et nous discutons généralement du pire des cas de complexité temporelle.

Cours recommandés : Tutoriel langage C

Complexité spatiale :

La complexité spatiale de l'algorithme n'est pas réellement un espace occupé , mais pour calculer le nombre d'unités spatiales auxiliaires dans tout l'espace algorithmique, ce qui n'a rien à voir avec l'ampleur du problème. La complexité spatiale S(n) d'un algorithme est définie comme l'ordre de grandeur de l'espace consommé par l'algorithme.

S(n)=o(f(n))

Si l'espace auxiliaire requis pour l'exécution de l'algorithme est une constante par rapport aux données d'entrée n, on l'appelle la complexité spatiale du algorithme L'espace auxiliaire est o(1);

La complexité spatiale de l'algorithme récursif : la profondeur de récursion n*l'espace auxiliaire requis pour chaque récursion. Si l'espace auxiliaire requis pour chaque récursion est une constante, le la complexité spatiale récursive est o (n).

L'équation de calcul de la complexité temporelle de l'algorithme récursif est une équation récursive :

Un exemple peut être considéré avant d'introduire l'arbre récursif :

T(n) = 2T(n/2) + n2

Itérer 2 fois pour obtenir :

T(n) = n2 + 2(2T(n/4) + (n/2) 2)

Vous pouvez également continuer à itérer et le développer complètement pour obtenir :

T(n) = n2 + 2((n/2) 2 +
2((n/22)2 + 2((n/23) 2 +
2((n/24) 2 +…+2((n/2i) 2 +
2T(n/2i + 1)))…))))……(1)

Et quand n/2i+ 1 == 1 , l'itération se termine.

Développez les parenthèses de l'équation (1), nous pouvons obtenir :

T(n) = n2 + 2(n/2)2 +
22(n/22) 2 + … + 2i(n/2i)2 +
2i+1T(n/2i+1)

Il s'agit d'une structure arborescente, à partir de laquelle la méthode de l'arbre récursif peut être dérivée.

(a)(b)(c)(d) sur la figure sont les étapes 1, 2, 3 et n respectivement dans la génération d'arbre récursive. Dans chaque nœud, l'élément libre actuel n2 est conservé, et les deux éléments récursifs T(n/2)
+ T(n/2) sont respectivement alloués à ses deux nœuds enfants, et ainsi de suite.

La somme de tous les nœuds du graphe est :

[1 + 1/2 + (1/2)2 + (1/2)3 + … + (1/2)i] n2 = 2n2

On peut voir que sa complexité temporelle est O(n2)

La règle de l'arbre récursif peut être obtenu comme :

(1) Le nœud de chaque couche est la valeur de f(n) dans T(n) = kT(n / m) + f(n) au actuel n/m;

(2) Le nombre de branches de chaque nœud est k

(3) Le côté droit de chaque couche marque la somme de tous les nœuds de la couche actuelle.

Autre exemple :

T(n) = T(n/3) + T(2n/3) + n

C'est le récursif L'arbre est comme indiqué ci-dessous :

On peut voir que la valeur de chaque couche est n, et le chemin le plus long de la racine au nœud feuille est :

Parce qu'à la fin La récursion s'arrête à (2/3)kn == 1. Puis

puis

, c'est-à-dire , T(n) = O(nlogn)　

En résumé, utilisez cette méthode pour résoudre la complexité de l'algorithme récursif :

f(n) = af(n/b) + d(n)

1. d(n) est une constante :

　

2 Lorsque d(n) = cn :

3. L'arbre de récursion peut être utilisé lorsque d(n) est dans d'autres cas. Effectuer une analyse.

Dans le deuxième cas, si la méthode diviser pour régner est utilisée pour améliorer l'algorithme d'origine, l'accent est mis sur l'utilisation de nouvelles méthodes de calcul pour réduire la valeur de a. ​

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!