Analyse d'exemples de complexité temporelle et spatiale Java

1. Efficacité des algorithmes

L'analyse de l'efficacité des algorithmes est divisée en deux types : le premier est l'efficacité temporelle et le second est l'efficacité spatiale. L’efficacité temporelle est appelée complexité temporelle, et l’efficacité spatiale est appelée complexité spatiale. La complexité temporelle mesure principalement la vitesse d'exécution d'un algorithme, tandis que la complexité spatiale mesure principalement l'espace supplémentaire requis par un algorithme. Au début du développement informatique, la capacité de stockage des ordinateurs était très faible. Nous nous soucions donc beaucoup de la complexité de l’espace. Cependant, après le développement rapide de l’industrie informatique, la capacité de stockage des ordinateurs a atteint un niveau très élevé. Nous n’avons donc plus besoin de prêter une attention particulière à la complexité spatiale d’un algorithme.

2. Complexité temporelle

1. Concept de complexité temporelle

Le temps que prend un algorithme est proportionnel au nombre d'exécutions de ses instructions. Le nombre d'exécutions d'opérations de base dans l'algorithme est la complexité temporelle de l'algorithme. C'est-à-dire que lorsque nous obtenons un code et examinons la complexité temporelle du code, nous trouvons principalement combien de fois le code avec les instructions les plus exécutées dans le code a été exécuté.

2. Représentation asymptotique du grand O

Regardez l'image et analysez :

Lorsque la valeur de N devient de plus en plus grande, les valeurs de 2N et 10 peuvent être ignorées.

En fait, lorsque nous calculons la complexité temporelle, nous n'avons pas réellement à calculer le nombre exact d'exécutions, mais seulement le nombre approximatif d'exécutions, nous utilisons donc ici la représentation asymptotique de Big O.

Notation Big O : C'est un symbole mathématique utilisé pour décrire le comportement asymptotique d'une fonction.

1. Remplacez toutes les constantes additives au moment de l'exécution par la constante 1.

2. Dans la fonction des temps d'exécution modifiés, seul le terme d'ordre le plus élevé est conservé.

3. Si le terme d'ordre le plus élevé existe et n'est pas 1, supprimez la constante multipliée par ce terme. Le résultat est l’ordre Big O.

Grâce à ce qui précède, nous constaterons que la représentation asymptotique de Big O supprime les éléments qui ont peu d'impact sur les résultats et exprime le nombre d'exécutions de manière concise et claire.

De plus, il existe des cas meilleurs, moyens et pires pour la complexité temporelle de certains algorithmes :

Pire cas : le nombre maximum d'exécutions (limite supérieure) pour toute taille d'entrée

Cas moyen : le nombre d'exécutions attendu pour n'importe quelle taille d'entrée

Meilleur cas : Nombre minimum d'exécutions (limite inférieure) pour n'importe quelle taille d'entrée

Par exemple : Recherche d'une donnée Situation : N/2 fois trouvées

En pratique, la situation générale se concentre sur la pire situation de fonctionnement de l'algorithme, donc la complexité temporelle de la recherche de données dans le tableau est O(N)

Complexité temporelle du calcul

Exemple 1 :

L'opération de base a été exécutée 2N+10 fois en dérivant le grand. O méthode de commande, on sait que la complexité temporelle est O(N)

Exemple 2 :

L'opération de base a été exécutée M+N fois, il y en a deux Pour les nombres inconnus M et N, la complexité temporelle est O(N+M)

Exemple 3 :

L'opération de base est effectuée 100 fois En dérivant la méthode du grand ordre O, la complexité temporelle est O(1)

Exemple 4 : Calculer la complexité temporelle. de tri à bulles

L'opération de base est exécutée N fois au mieux et (N*(N-1))/2 fois au pire En dérivant la méthode du grand O + complexité temporelle De manière générale, au pire, le. la complexité temporelle est O(N^2

Exemple 5 : Complexité temporelle de la recherche binaire

L'opération de base est effectuée une fois au mieux et O(logN) fois au pire, et la complexité temporelle est O(logN) ps : Dans l'analyse algorithmique, logN signifie que la base est 2 et le logarithme est N. À certains endroits, il est écrit comme lgN (il est recommandé d'expliquer comment logN est calculé via la recherche en origami) (car la recherche binaire exclut à chaque fois. Drop la moitié des valeurs inappropriées, et les valeurs restantes seront divisées en deux parties : n/2 Les valeurs restantes seront divisées en deux parties : n/2/2 = n/4)

Exemple 6 : Calculer la complexité temporelle de la récursion factorielle

Complexité temporelle de la récursion = Nombre de récursions * Nombre de fois que chaque récursion est exécutée

On découvre par calcul et analyse que l'opération de base est récursive N fois, et la complexité temporelle est O(N)

Exemple 7 : Calcul de la complexité temporelle de la récursion de Fibonacci Degré

.

Grâce au calcul et à l'analyse, nous avons constaté que l'opération de base est récursive 2^N fois et que la complexité temporelle est O(2^N).

Règle :

2^0+2^1+2^2+2^3……2^(n-(n-1))

Somme d'une séquence géométrique

a1 représente le premier élément, q est égal à 2, 1(1-2^n)/-1, ce qui équivaut à 2^n+1, donc la complexité temporelle est O(2^n)

Trois.

La complexité spatiale est une mesure de la quantité d'espace de stockage qu'un algorithme occupe temporairement pendant son fonctionnement. La complexité spatiale n'est pas le nombre d'octets d'espace occupés par le programme, car cela n'a pas beaucoup de sens, donc la complexité spatiale est calculée par le nombre de variables. Les règles de calcul de la complexité spatiale sont fondamentalement similaires à la complexité pratique, et la notation asymptotique grand O est également utilisée.

Exemple 1 : Calculer la complexité spatiale du tri à bulles

utilise un espace supplémentaire constant, donc la complexité spatiale est O(1)

Exemple 2 : Calculer la complexité spatiale de Fibonacci

N espaces sont ouverts dynamiquement et la complexité spatiale est O(N)

Exemple 3 : Calculez la complexité spatiale de la récursion factorielle

L'appel récursif est effectué N fois et N cadres de pile sont ouverts, chaque cadre de pile utilise un quantité d'espace constante. La complexité spatiale est O(N)

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!