2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Il existe de nombreuses façons et méthodes pour résoudre le même problème d'algorithme. Le résultat final est le même et correct, mais l'efficacité peut varier.
Tout comme partir du même endroit et arriver à un autre endroit, les moyens d'y parvenir incluent les avions, les trains, les voitures privées... mais le temps mis est différent et l'économie est également différente.
Une fois l’algorithme écrit dans un programme exécutable, son exécution nécessite des ressources en temps et en espace (mémoire). Ainsi, la qualité d’un algorithme se mesure généralement à partir de deux dimensions : le temps et l’espace, à savoir la complexité temporelle et la 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 pour exécuter un algorithme.
Au début du développement informatique, les ordinateurs avaient une très petite capacité de stockage. 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 d’accorder une attention particulière à la complexité spatiale d’un algorithme.
Lorsque je joue à certains jeux, mon téléphone sera très chaud lorsque je joue à certains jeux, et certains jeux ne seront pas chauds si j'y joue, ce qui est indissociable de la complexité. Mon téléphone exécute un algorithme simple et il s'exécute rapidement, mais il. est compliqué à exécuter. Algorithme, pour garantir que le temps est moins utilisé, la pleine puissance doit être activée, donc il fera chaud.
Définition : En informatique, la complexité temporelle d'un algorithme est une formule fonctionnelle T(N), qui décrit quantitativement le temps d'exécution de l'algorithme. La complexité temporelle mesure l'efficacité temporelle d'un programme, alors pourquoi ne pas calculer la durée d'exécution du programme ?
- Parce que la durée d'exécution du programme est liée à la configuration de l'environnement de compilation et de la machine en cours d'exécution, par exemple, si un programme algorithmique est compilé avec un ancien compilateur ou compilé avec un nouveau compilateur, la durée d'exécution sera différente sur la même machine.
- Le même programme algorithmique a des temps d'exécution différents en utilisant une ancienne machine à faible configuration et une nouvelle machine à haute configuration.
- Et le temps ne peut être testé qu'une fois le programme écrit, et non calculé et évalué par une réflexion théorique avant d'écrire le programme.
Par conséquent, lors de l’évaluation du degré d’affectation du temps d’un algorithme, le temps d’exécution de l’algorithme n’est pas pris en compte, mais uniquement le nombre d’instructions exécutées.
Cas:
// 请计算⼀下Func1中++count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
Par l’observation :
Nombre d'opérations de base effectuées par Func1 :
T(N)=N2+ 2*N + 10
En pratique, lorsque nous calculons la complexité temporelle, nous ne calculons pas le nombre exact d'exécutions du programme. Le calcul du nombre exact d'exécutions est toujours très fastidieux (différentes phrases de code de programme auront un nombre différent d'instructions compilées (comme). ceci), le calcul du nombre exact d'exécutions a peu d'importance, car nous voulons seulement comparer le niveau de croissance du programme algorithmique dans le calcul de la complexité temporelle, c'est-à-dire la différence de T(N) lorsque N continue d'augmenter. Nous avons vu ci-dessus que les constantes et les termes d'ordre inférieur ont peu d'impact sur les résultats lorsque N continue de croître, il suffit donc de calculer le nombre approximatif d'exécutions que le programme peut représenter pour augmenter l'ordre de grandeur. habituellement utilisé Utilisez la notation asymptotique de Big O.
La complexité spatiale est également une expression mathématique, qui est l'espace supplémentaire temporairement alloué en raison des besoins de l'algorithme pendant le fonctionnement d'un algorithme.
La complexité spatiale n'est pas le nombre d'octets d'espace occupés par le programme. Parce que dans des circonstances normales, la taille de chaque objet ne différera pas beaucoup, la complexité spatiale est donc 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 Big O est également utilisée.
Remarque : L'espace de pile requis lors de l'exécution de la fonction (stockage des paramètres, des variables locales, certaines informations de registre, etc.) a été déterminé lors de la compilation, la complexité de l'espace est donc principalement déterminée par l'espace supplémentaire explicitement demandé par la fonction pendant l'exécution. . Bien sûr
L'espace n'est pas un facteur clé dans le développement informatique actuel, mais un gaspillage excessif entraînera des problèmes inutiles.
Notation Big O : C'est un symbole mathématique utilisé pour décrire le comportement asymptotique des fonctions.
Règles pour passer à la notation asymptotique Big O :
- 1. Dans la formule fonctionnelle de complexité temporelle T(N), seuls les termes d'ordre supérieur sont conservés et les termes d'ordre inférieur sont supprimés, car lorsque N continue d'augmenter,
L’impact des termes d’ordre inférieur sur les résultats est de plus en plus faible, et lorsque N est infini, ils peuvent être ignorés.- 2. Si le terme d'ordre le plus élevé existe et n'est pas 1, supprimez le coefficient constant de ce terme, car à mesure que N continue d'augmenter, ce coefficient
L’impact sur les résultats est de plus en plus faible, et lorsque N est infini, il peut être ignoré.- 3. S'il n'y a pas d'éléments liés à N dans T(N) mais seulement des éléments constants, remplacez toutes les constantes additives par la constante 1.
Dans le pire des cas : nombre maximum d'exécutions (limite supérieure) pour n'importe quelle taille d'entrée
Cas moyen : nombre d'exécutions attendu pour n'importe quelle taille d'entrée
Meilleur cas : nombre minimum d'exécutions (limite inférieure) pour toute taille d'entrée
En pratique, la représentation asymptotique de Big O se concentre généralement sur la borne supérieure de l’algorithme, qui constitue la pire situation de fonctionnement.
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
++count;
}
}
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
complexité temporelle :
Omettez le code qui s'exécute une fois, tel que count=0, ce code.
Conserver le nombre d'exécutions de code ayant un impact important sur le temps d'exécution
Le nombre d'exécutions de la première boucle est une exécution en double boucle de NN
La deuxième boucle est une couche de temps d'exécution de boucle 2N
Le troisième cycle est 10 fois
La somme du nombre d'exécutions est T(N)=N2+2*N+10
Big O représente la complexité temporelle, rejetez le petit impact et prenez la limite
SUR2)
Complexité spatiale :
La fonction Func1 s'applique pour la taille de l'espace. Par exemple, int count = 0, elle s'applique pour la taille de l'espace de type int, elle s'applique également pour l'espace de type int.
Ces deux espaces sont également utilisés dans la boucle sans espace applicatif supplémentaire.
La taille de l'espace d'application est constante
La complexité spatiale exprimée en Big O est :
O(1)
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%dn", count);
}
complexité temporelle :
Le nombre d’exécutions du code est supérieur à la première boucle, qui est N*2.
La deuxième boucle s'exécute 10 fois
Utilisez le grand O pour représenter la complexité temporelle. Le plus grand impact est 2*N. Le terme de coefficient précédent est omis :
SUR)
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++k)
{
++count;
}
for (int k = 0; k < N; ++
k)
{
++count;
}
printf("%dn", count);
}
complexité temporelle
Il y a deux inconnues, et le plus grand impact se situe sur les deux boucles
La première boucle s'exécute M fois
La deuxième boucle s'exécute N fois
Ce devrait être un nombre inconnu. Je ne sais pas lequel est le plus grand et lequel est le plus petit, je ne l’oublierai pas.
O(M+N)
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%dn", count);
}
complexité temporelle :
Le plus grand impact ici est un cycle
Le nombre de fois que la boucle s'exécute est de 100
est une constante fixe
O(1)
const char* strchr(const char* str, int character)
{
const char* p_begin = str;
while (*p_begin != character)
{
if(*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
La fonction accomplie par cette fonction est de trouver l'indice d'un caractère dans un tableau.
Le nombre de courses ici est incertain
Il est possible de trouver F(N)=1 en une seule fois
Il est possible de trouver F(N)=N/2 au milieu
Il peut être trouvé à la fin, ou NULL est renvoyé s'il n'est pas trouvé, F(N)=N
Big O prend le pire des cas :
La complexité temporelle est O(N)
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
Ce nombre d'exécutions est lié à la taille de n, mais il ne boucle pas n fois. Cela devrait être dû au fait que la variable de boucle sera multipliée par 2 pendant la boucle et que la boucle sautera rapidement après avoir été exécutée dix fois. la valeur de la variable de boucle cnt atteindra 1024.
En supposant que le nombre de cycles est x, alors 2X=n
x=logn
La complexité temporelle est donc : O(longn)
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if(exchange == 0)
break;
}
}
Cette fonction complète le tri ascendant des bulles
Il y a une boucle ici. Cette boucle est une boucle imbriquée à deux niveaux.
Le nombre de boucles n'est pas défini
Le pire des cas est que la boucle externe s'exécute n fois
Ensuite, la boucle interne exécutera (n-1)+(n-2)+(n-3)+……+2+1+0
est une suite arithmétique dont la somme est :
La complexité temporelle est : O(N)
Complexité spatiale :
Il n'y a pas d'espace d'application supplémentaire et l'espace appliqué est constant.
O(1)
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
complexité temporelle :
Récursif N fois
La complexité temporelle est donc : O(N)
Complexité spatiale :
Chaque fois que vous récidivez, vous devez demander une place.
Récursif N fois et appliqué pour N fois de l'espace.
La complexité spatiale est : O(N)
Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.
