Partage de technologie

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Préface

Si vous voulez savoir ce qu'est la complexité espace/temps, vous devez savoir ce qu'est une structure de données.

Cela peut être compris à deux niveaux. Les données existent partout dans nos vies, comme les événements internationaux qui sont des sujets brûlants pour Douyin, le retrait de l'armure de Yongzheng, etc. Ce que nos utilisateurs peuvent voir, ce sont les données que Douyin stocke dans le serveur backend. Mais ces données ont toutes une caractéristique, c'est-à-dire qu'elles figurent toutes sur la liste de recherche rapide de Douyin, et cette liste est structurée pour garantir que les données se trouvent dans un emplacement fixe pour que les utilisateurs puissent les parcourir.

De plus, avec les structures de données, les algorithmes sont indissociables. Eh bien, comme nous venons de le dire, une structure de données stocke régulièrement les données dans une structure, donc comment accéder efficacement aux données de la structure est un algorithme.

complexité temporelle

Avec les algorithmes, il existe une complexité temporelle et une complexité spatiale. La mémoire des ordinateurs étant de plus en plus grande, la complexité temporelle est plus importante que la complexité spatiale.Alors commençons par comprendre la complexité temporelle

concept

Complexité temporelle, le mot le plus important est temps, le temps fait ici référence au moment où un programme est en cours d'exécution. Si la complexité temporelle est moindre, alors l'algorithme s'avère meilleur.Le calcul de complexité temporelle est exprimé par la formule fonctionnelle T(N)

Alors pourquoi ne pas calculer à l'avance la complexité temporelle de ce programme et écrire le code de la solution optimale ? Cela implique des problèmes informatiques.

1. Parce que la durée d'exécution du programme est liée à l'environnement de compilation et à la configuration de la machine en cours d'exécution, par exemple, un programme algorithmique utilise un ancien compilateur.
   La compilation avec un nouveau compilateur et la compilation avec un nouveau compilateur ont des durées d'exécution différentes sur la même machine.
2. 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.
3. 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.

Regardons un morceau de code :

// 请计算⼀下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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Si vous regardez ce code en fonction du nombre d'exécutions de count, il devrait être :
T (N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

À ce moment-là, quelqu'un a dit, est-ce que cela int count=0 ne compte pas ?

Ici, nous sous-estimons trop notre ordinateur. Le processeur de notre ordinateur peut s'exécuter des centaines de millions de fois par seconde. Bien sûr, ce petit temps peut être ignoré. Par conséquent, la complexité temporelle que nous avons calculée n’est pas exacte, il ne s’agit que d’une estimation approximative. Pour le moment, nous utilisons un nouveau symbole pour la représenter.

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 ; il est utilisé ici pour représenter la complexité temporelle estimée.

Alors, est-ce que ça compte toujours comme T(N) ici ? Si c’est le cas, nous n’avons pas besoin d’utiliser un autre symbole pour le représenter. Cela implique les règles pour compter 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 le résultat devient de plus en plus petit. Lorsque N devient infini, il peut être ignoré.
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 de croître, ce coefficient aura de moins en moins d'influence sur le résultat. 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.

Ensuite, regardez ce qui précède T(N)=N^ 2 + 2 ∗ N + 10. L'ordre le plus élevé ici est N2, donc en supprimant les autres ordres bas, la complexité est (ON^2)

Hachoir à petite échelle

// 计算Func3的时间复杂度？
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Ici T(N)=M+N, puis calculons à nouveau O(N) M et N ici sont tous deux du même ordre, donc ils ne sont pas conformes à la première règle, et ne correspondent pas aux deuxième et troisième règles. , donc o(N+M), alors quelqu'un a demandé : et si N est plus grand que M, devrait-il être O(N). La question ici est, comment savez-vous que N est plus grand que M ? Et si M est plus grand que N, alors nous restons ici juste par mesure de sécurité.

// 计算strchr的时间复杂度？
const char * strchr ( const char
 * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Ici, nous recherchons la position du caractère dans str. Ici, j'ajouterai un point de connaissance :

• Notre calcul O correspond généralement à la complexité la plus défavorable d’un algorithme.
  Ici, il peut être divisé en trois niveaux de complexité :
  1. Meilleur scénario
  Pour rechercher le caractère en première position de la chaîne, alors :
  F (N) = 1, la complexité est o(1)

2. Situation moyenne :
Pour trouver le caractère au milieu de la chaîne, alors :
F (N) = N/2,O(N/2)

3. Le pire des cas
Pour rechercher le caractère à la dernière position de la chaîne, alors :
F (N) = N,O(N)

// 计算BubbleSort的时间复杂度？
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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Dans le pire des cas, parce que l'ordre élevé est conservé et que n/2 est supprimé (le premier élément) et que le coefficient (le deuxième élément) est ignoré, il est ON^2

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
1
2
3
4
5
6
7
8

Lorsque n=2, le nombre d'exécutions est de 1
Lorsque n=4, le nombre d'exécutions est de 2
Lorsque n=16, le nombre d'exécutions est de 4
En supposant que le nombre d'exécutions est x, alors 2
x = n
Donc le nombre d'exécutions : x = log n
Par conséquent : la complexité temporelle dans le pire des cas de func5 est :
O(log2 ^n)

Différents livres ont des méthodes d'expression différentes. Les méthodes d'écriture ci-dessus ne sont pas très différentes. Nous vous recommandons d'utiliser log n.

complexité de l'espace

Ce qu'il convient de noter à propos de la complexité spatiale, c'est que sa représentation de calcul est également représentée par O et que ses règles suivent les trois mêmes règles que la complexité temporelle.

Avis

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, de sorte que la complexité de l'espace est principalement déterminée par l'espace supplémentaire explicitement demandé par la fonction pendant l'exécution.

Exemple 1:

// 计算BubbleSort的时间复杂度？
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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Le cadre de la pile de fonctions a été déterminé lors de la compilation.
Il vous suffit de faire attention à l'espace supplémentaire demandé par la fonction lors de l'exécution.
Un espace d'application supplémentaire pour BubbleSort est
Il existe un nombre limité de variables locales telles que l'échange, qui utilise une quantité constante d'espace supplémentaire.
La complexité spatiale est donc O(1)