Un article pour parler de la complexité temporelle et spatiale de l'algorithme

Cet article découvrira l'algorithme et présentera la complexité temporelle et spatiale de l'algorithme. J'espère qu'il sera utile à tout le monde !

L'algorithme fait référence à un ensemble de méthodes utilisées pour manipuler les données et résoudre les problèmes du programme. Pour un même problème, en utilisant des algorithmes différents, le résultat final peut être le même, mais les ressources et le temps consommés dans le processus seront très différents.

Alors, comment devrions-nous mesurer les avantages et les inconvénients des différents algorithmes ?

Considérez-le principalement sous les deux dimensions « temps » et « espace » occupées par l'algorithme.

• Dimension temporelle : fait référence au temps consommé pour exécuter l'algorithme actuel. Nous utilisons généralement « complexité temporelle » pour le décrire.

• Dimension spatiale : fait référence à la quantité d'espace mémoire requise pour exécuter l'algorithme actuel. Nous utilisons généralement la « complexité spatiale » pour le décrire.

Par conséquent, évaluer l’efficacité d’un algorithme dépend principalement de sa complexité temporelle et de sa complexité spatiale. Cependant, parfois, le temps et l'espace consistent à « avoir le gâteau et le manger aussi » et vous ne pouvez pas avoir les deux, nous devons donc trouver un point d'équilibre.

Permettez-moi de vous présenter respectivement les méthodes de calcul de la « complexité temporelle » et de la « complexité spatiale ».

1. Complexité temporelle

Nous voulons connaître la « complexité temporelle » d'un algorithme. La première façon à laquelle beaucoup de gens pensent est d'exécuter le programme d'algorithme une fois, puis le temps qu'il consomme sera naturellement connu.

Est-ce que cette méthode est acceptable ? Bien sûr, c’est possible, mais cela présente aussi de nombreux inconvénients.

Cette méthode est très sensible à l'influence de l'environnement d'exploitation. Les résultats exécutés sur une machine hautes performances seront très différents des résultats exécutés sur une machine peu performante. Et cela a aussi beaucoup à voir avec l’ampleur des données utilisées lors des tests. De plus, lorsque nous avons écrit l’algorithme, nous n’avions toujours aucun moyen de l’exécuter complètement.

Par conséquent, une autre méthode plus générale apparaît : " Notation Big O", c'est-à-dire T(n) = O(f(n))

Regardons d'abord un exemple :

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

Par " Notation Big O", la complexité temporelle de ce code est : O(n), pourquoi ?

En notation Big O, la formule de complexité temporelle est : T(n) = O( f(n) ), où f(n) représente la somme du nombre de fois où chaque ligne de code est exécutée, et O représente une relation proportionnelle. Le nom complet de cette formule est : Complexité temporelle asymptotique de l'algorithme.

Continuons à regarder l'exemple ci-dessus. Supposons que le temps d'exécution de chaque ligne de code soit le même. Nous utilisons 1 temps de particule pour l'exprimer. Ensuite, la première ligne de cet exemple prend 1 temps de particule, et le temps d'exécution. de la troisième ligne est de 1 temps de particule. est de n temps de particule, et le temps d'exécution de la quatrième ligne est également de n temps de particule (les deuxième et cinquième lignes sont des symboles, ignorez-les pour l'instant), alors le temps total est de 1 temps de particule. + n temps de particule + n temps de particule, soit (1 +2n) temps de particule, soit : T(n) = (1+2n)*temps de particule. À partir de ce résultat, on peut voir que la consommation de temps de cette particule. L'algorithme change avec le changement de n. Par conséquent, nous pouvons simplifier Exprimer la complexité temporelle de cet algorithme comme suit : T(n) = O(n)

Pourquoi peut-il être simplifié de cette manière parce que la notation grand O n'est pas utilisée ? pour représenter véritablement le temps d'exécution de l'algorithme. Il est utilisé pour représenter la tendance à la croissance du temps d'exécution du code.

Donc, dans l'exemple ci-dessus, si n est infini, la constante 1 dans T(n) = time(1+2n) n'a pas de sens, et le multiple 2 n'a pas non plus de sens. Par conséquent, cela peut être simplement simplifié en T(n) = O(n).

Les métriques courantes de complexité temporelle sont :

• Ordre constant O(1)

• Ordre logarithmique O(logN)

• Ordre linéaire O(n)

• Ordre logarithmique linéaire O (nlogN)

• ordre carré O(n²)

• ordre cube O(n³)

• Kème ordre O(n^k)

• ordre exponentiel (2^n)

La complexité temporelle de de haut en bas devient de plus en plus grand et l'efficacité d'exécution devient de plus en plus faible.

Ce qui suit sélectionne quelques-uns des plus couramment utilisés pour expliquer (pas dans un ordre strict) :

• Ordre constant O(1)

Peu importe le nombre de lignes de code exécutées, comme tant qu'il n'y a pas de structures complexes telles que des boucles , alors la complexité temporelle de ce code est O(1), comme :

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

Lorsque le code ci-dessus est exécuté, sa consommation n'augmente pas avec la croissance d'une certaine variable, donc peu importe le nombre de ces codes, même s'il s'agit de dizaines de milliers ou de centaines de milliers de lignes, sa complexité temporelle peut être exprimée par O(1).

• Ordre linéaire O(n)

Cela a été expliqué dans le premier exemple de code, tel que :

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

Dans ce code, le code dans la boucle for sera exécuté n fois, Par conséquent, le temps qu'il consomme change à mesure que n change, ce type de code peut donc utiliser O(n) pour représenter sa complexité temporelle.

• Ordre logarithmique O(logN)

Regardons d'abord le code :

int i = 1;
while(i<n)
{
    i = i * 2;
}

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n

也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

• 线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

就拿上面的代码加一点修改来举例：

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

• 平方阶O(n²)

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

举例：

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)

如果将其中一层循环的n改成m，即：

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

那它的时间复杂度就变成了 O(m*n)

• 立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

除此之外，其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法，有点复杂，这里就不展开了。

二、空间复杂度

既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：

• 空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

举例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

• 空间复杂度 O(n)

我们先看一个代码：

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = 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!