Comment trouver la complexité temporelle d'un algorithme

La question

Comment trouver la complexité temporelle d'un algorithme?

Qu'est-ce que j'ai fait avant de poster une question sur SO?

J'ai traversé ça , ça et bien d'autres liens

Mais nulle part où j'ai pu trouver une explication claire et simple sur la façon de calculer la complexité du temps.

Qu'est ce que je sais ?

Dites pour un code aussi simple que celui ci-dessous:

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

Dites pour une boucle comme celle ci-dessous:

for (int i = 0; i < N; i++) {        
    Console.Write('Hello World !');
}

int i = 0; Cela ne sera exécuté qu'une seule fois . Le temps est effectivement calculé i=0et non la déclaration.

i <N; Cela sera exécuté N + 1 fois

i ++; Cela sera exécuté N fois

Ainsi, le nombre d'opérations requises par cette boucle est

{1+ (N + 1) + N} = 2N + 2

Remarque: Cela peut encore être faux, car je ne suis pas sûr de ma compréhension du calcul de la complexité temporelle

Ce que je veux savoir ?

Ok, donc ces petits calculs de base, je pense que je sais, mais dans la plupart des cas, j'ai vu la complexité du temps comme

O (N), O (n2), O (log n), O (n!) .... et bien d' autres ,

Quelqu'un peut-il m'aider à comprendre comment calculer la complexité temporelle d'un algorithme? Je suis sûr qu'il y a beaucoup de débutants comme moi qui veulent le savoir.

Comment trouver la complexité temporelle d'un algorithme

Vous additionnez le nombre d'instructions machine qu'il exécutera en fonction de la taille de son entrée, puis simplifiez l'expression au terme le plus grand (lorsque N est très grand) et pouvez inclure n'importe quel facteur constant de simplification.

Par exemple, voyons comment nous simplifions 2N + 2les instructions machine pour décrire cela comme juste O(N).

Pourquoi supprimons-nous les deux 2s?

Nous nous intéressons aux performances de l'algorithme lorsque N devient grand.

Considérez les deux termes 2N et 2.

Quelle est l'influence relative de ces deux termes lorsque N devient grand? Supposons que N soit un million.

Ensuite, le premier terme est de 2 millions et le second terme n'est que de 2.

Pour cette raison, nous supprimons tous les termes sauf les plus gros pour les gros N.

Alors maintenant, nous sommes passés de 2N + 2à 2N.

Traditionnellement, nous ne nous intéressons qu'aux performances jusqu'à des facteurs constants .

Cela signifie que nous ne nous soucions pas vraiment s'il y a un multiple constant de différence de performance lorsque N est grand. L'unité de 2N n'est pas bien définie de toute façon. Nous pouvons donc multiplier ou diviser par un facteur constant pour arriver à l'expression la plus simple.

Alors 2Ndevient juste N.

Ceci est un excellent article: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

La réponse ci-dessous est copiée d'en haut (au cas où l'excellent lien tomberait en panne)

La métrique la plus courante pour calculer la complexité temporelle est la notation Big O. Cela supprime tous les facteurs constants afin que le temps de fonctionnement puisse être estimé par rapport à N lorsque N approche de l'infini. En général, vous pouvez le voir comme ceci:

statement;

Est constant. Le temps d'exécution de la déclaration ne changera pas par rapport à N.

for ( i = 0; i < N; i++ )
     statement;

Est linéaire. Le temps de parcours de la boucle est directement proportionnel à N. Lorsque N double, il en est de même du temps de parcours.

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

Est quadratique. Le temps de fonctionnement des deux boucles est proportionnel au carré de N. Lorsque N double, le temps de fonctionnement augmente de N * N.

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

Est logarithmique. Le temps d'exécution de l'algorithme est proportionnel au nombre de fois où N peut être divisé par 2. En effet, l'algorithme divise la zone de travail en deux à chaque itération.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

Est N * log (N). Le temps d'exécution est constitué de N boucles (itératives ou récursives) logarithmiques, donc l'algorithme est une combinaison de linéaire et de logarithmique.

En général, faire quelque chose avec chaque élément dans une dimension est linéaire, faire quelque chose avec chaque élément dans deux dimensions est quadratique, et diviser la zone de travail en deux est logarithmique. Il existe d'autres mesures Big O telles que cubique, exponentielle et racine carrée, mais elles ne sont pas aussi courantes. La notation Big O est décrite comme O ( <type> )où se <type>trouve la mesure. L'algorithme de tri rapide serait décrit comme suit O ( N * log ( N ) ).

Notez que rien de tout cela n'a pris en compte les meilleures, moyennes et pires mesures. Chacun aurait sa propre notation Big O. Notez également qu'il s'agit d'une explication TRÈS simpliste. Big O est le plus courant, mais c'est aussi plus complexe que je l'ai montré. Il existe également d'autres notations telles que gros oméga, petit o et gros thêta. Vous ne les rencontrerez probablement pas en dehors d'un cours d'analyse d'algorithmes. ;)

Tiré d'ici - Introduction à la complexité temporelle d'un algorithme

1. Introduction

En informatique, la complexité temporelle d'un algorithme quantifie le temps nécessaire à un algorithme pour s'exécuter en fonction de la longueur de la chaîne représentant l'entrée.

2. Notation Big O

La complexité temporelle d'un algorithme est généralement exprimée en utilisant la notation O, qui exclut les coefficients et les termes d'ordre inférieur. Lorsqu'elle est exprimée de cette manière, la complexité temporelle est décrite comme étant asymptotique, c'est-à-dire lorsque la taille d'entrée va à l'infini.

Par exemple, si le temps requis par un algorithme sur toutes les entrées de taille n est au plus 5n ³ + 3n, la complexité temporelle asymptotique est O (n ³ ). Plus sur cela plus tard.

Quelques exemples supplémentaires:

• 1 = O (n)
• n = O (n ² )
• log (n) = O (n)
• 2 n + 1 = O (n)

3. O (1) Temps constant:

Un algorithme est censé fonctionner en temps constant s'il nécessite le même temps quelle que soit la taille d'entrée.

Exemples:

• tableau: accès à n'importe quel élément
• pile de taille fixe: méthodes push et pop
• file d'attente de taille fixe: méthodes de mise en file d'attente et de retrait de file d'attente

4. O (n) Temps linéaire

On dit qu'un algorithme s'exécute en temps linéaire si son exécution en temps est directement proportionnelle à la taille d'entrée, c'est-à-dire que le temps croît linéairement à mesure que la taille d'entrée augmente.

Considérez les exemples suivants, ci-dessous je recherche linéairement un élément, celui-ci a une complexité temporelle de O (n).

int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
    if(find == numbers[i])
    {
        return;
    }
}

Plus d'exemples:

• Tableau: recherche linéaire, déplacement, recherche d'un minimum, etc.
• ArrayList: contient la méthode
• File d'attente: contient la méthode

5. O (log n) Temps logarithmique:

On dit qu'un algorithme s'exécute en temps logarithmique si son exécution temporelle est proportionnelle au logarithme de la taille d'entrée.

Exemple: recherche binaire

Rappelez-vous le jeu des «vingt questions» - la tâche consiste à deviner la valeur d'un nombre caché dans un intervalle. Chaque fois que vous faites une supposition, on vous dit si votre supposition est trop élevée ou trop basse. Le jeu de vingt questions implique une stratégie qui utilise votre nombre de suppositions pour réduire de moitié la taille de l'intervalle. Ceci est un exemple de la méthode générale de résolution de problèmes connue sous le nom de recherche binaire

6. O (n ² ) Temps quadratique

On dit qu'un algorithme s'exécute en temps quadratique si son exécution temporelle est proportionnelle au carré de la taille d'entrée.

Exemples:

• Tri des bulles
• Tri de sélection
• Tri par insertion

7. Quelques liens utiles

• Idées fausses Big-O
• Déterminer la complexité de l'algorithme
• Big O Cheat Sheet

Bien qu'il existe de bonnes réponses à cette question. Je voudrais donner une autre réponse ici avec plusieurs exemples de loop.

• O (n) : la complexité temporelle d'une boucle est considérée comme O (n) si les variables de la boucle sont incrémentées / décrémentées d'une quantité constante. Par exemple, les fonctions suivantes ont une complexité temporelle O (n) .

  // Here c is a positive integer constant   
  for (int i = 1; i <= n; i += c) {  
      // some O(1) expressions
  }
  
  for (int i = n; i > 0; i -= c) {
      // some O(1) expressions
  }
  

• O (n ^ c) : la complexité temporelle des boucles imbriquées est égale au nombre de fois que l'instruction la plus interne est exécutée. Par exemple, les boucles d'échantillonnage suivantes ont une complexité temporelle O (n ^ 2)

  for (int i = 1; i <=n; i += c) {
     for (int j = 1; j <=n; j += c) {
        // some O(1) expressions
     }
  }
  
  for (int i = n; i > 0; i += c) {
     for (int j = i+1; j <=n; j += c) {
        // some O(1) expressions
  }
  

  Par exemple, le tri de sélection et le tri d'insertion ont une complexité temporelle O (n ^ 2) .

• O (Logn) La complexité temporelle d'une boucle est considérée comme O (Logn) si les variables de la boucle sont divisées / multipliées par une quantité constante.

  for (int i = 1; i <=n; i *= c) {
     // some O(1) expressions
  }
  for (int i = n; i > 0; i /= c) {
     // some O(1) expressions
  }
  

  Par exemple, la recherche binaire a une complexité temporelle O (Logn) .

• O (LogLogn) La complexité temporelle d'une boucle est considérée comme O (LogLogn) si les variables de la boucle sont réduites / augmentées de façon exponentielle d'une quantité constante.

  // Here c is a constant greater than 1   
  for (int i = 2; i <=n; i = pow(i, c)) { 
     // some O(1) expressions
  }
  //Here fun is sqrt or cuberoot or any other constant root
  for (int i = n; i > 0; i = fun(i)) { 
     // some O(1) expressions
  }
  

Un exemple d'analyse de complexité temporelle

int fun(int n)
{    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j += i)
        {
            // Some O(1) task
        }
    }    
}

Analyse :

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

Ainsi, la complexité temporelle totale de l'algorithme ci-dessus est (n + n/2 + n/3 + … + n/n), qui devientn * (1/1 + 1/2 + 1/3 + … + 1/n)

L'important à propos des séries (1/1 + 1/2 + 1/3 + … + 1/n)est égal à O (Logn) . La complexité temporelle du code ci-dessus est donc O (nLogn) .

Réf: 1 2 3

Complexité temporelle avec exemples

1 - Opérations de base (arithmétique, comparaisons, accès aux éléments du tableau, affectation): Le temps d'exécution est toujours constant O (1)

Exemple :

read(x)                               // O(1)
a = 10;                               // O(1)
a = 1.000.000.000.000.000.000         // O(1)

2 - Instruction if then else: en prenant uniquement le temps de fonctionnement maximal à partir de deux ou plusieurs instructions possibles.

Exemple:

age = read(x)                               // (1+1) = 2
if age < 17 then begin                      // 1
      status = "Not allowed!";              // 1
end else begin
      status = "Welcome! Please come in";   // 1
      visitors = visitors + 1;              // 1+1 = 2
end;

Ainsi, la complexité du pseudo-code ci-dessus est T (n) = 2 + 1 + max (1, 1 + 2) = 6. Ainsi, son grand oh est toujours constant T (n) = O (1).

3 - Boucle (pour, pendant, répéter): Le temps d'exécution de cette instruction est le nombre de boucles multiplié par le nombre d'opérations à l'intérieur de cette boucle.

Exemple:

total = 0;                                  // 1
for i = 1 to n do begin                     // (1+1)*n = 2n
      total = total + i;                    // (1+1)*n = 2n
end;
writeln(total);                             // 1

Ainsi, sa complexité est T (n) = 1 + 4n + 1 = 4n + 2. Ainsi, T (n) = O (n).

4 - Boucle imbriquée (boucle à l'intérieur de la boucle): Puisqu'il y a au moins une boucle à l'intérieur de la boucle principale, le temps d'exécution de cette instruction a utilisé O (n ^ 2) ou O (n ^ 3).

Exemple:

for i = 1 to n do begin                     // (1+1)*n  = 2n
   for j = 1 to n do begin                  // (1+1)n*n = 2n^2
       x = x + 1;                           // (1+1)n*n = 2n^2
       print(x);                            // (n*n)    = n^2
   end;
end;

Temps de course commun

Il existe certains temps d'exécution courants lors de l'analyse d'un algorithme:

1. O (1) - Temps constant Le temps constant signifie que le temps de fonctionnement est constant, il n'est pas affecté par la taille d'entrée .

2. O (n) - Temps linéaire Lorsqu'un algorithme accepte n tailles d'entrée, il effectue également n opérations.

3. O (log n) - L'algorithme de temps logarithmique qui a le temps d'exécution O (log n) est légèrement plus rapide que O (n). Généralement, l'algorithme divise le problème en sous-problèmes de même taille. Exemple: algorithme de recherche binaire, algorithme de conversion binaire.

4. O (n log n) - Temps linéarithmique Ce temps d'exécution se trouve souvent dans les «algorithmes de division et de conquête» qui divisent le problème en sous-problèmes de manière récursive puis les fusionnent en n temps. Exemple: algorithme de tri par fusion.

5. O (n ² ) - Algorithme de tri des bulles à aspect temporel quadratique!

6. O (n ³ ) - Temps cubique Il a le même principe avec O (n ² ).

7. O (2 ⁿ ) - Temps exponentiel Il est très lent lorsque l'entrée augmente, si n = 1000 000, T (n) serait 21 000 000. L'algorithme Brute Force a ce temps d'exécution.

8. O (n!) - Temps factoriel LE PLUS LENT !!! Exemple: problème du vendeur de voyages (TSP)

Tiré de cet article . Très bien expliqué devrait donner lecture.

Lorsque vous analysez du code, vous devez l'analyser ligne par ligne, en comptant chaque opération / en reconnaissant la complexité du temps, à la fin, vous devez le additionner pour obtenir une image complète.

Par exemple, vous pouvez avoir une boucle simple avec une complexité linéaire , mais plus tard dans ce même programme, vous pouvez avoir une boucle triple qui a une complexité cubique , donc votre programme aura une complexité cubique . L'ordre de croissance des fonctions entre en jeu ici.

Voyons quelles sont les possibilités de complexité temporelle d'un algorithme, vous pouvez voir l'ordre de croissance que j'ai mentionné ci-dessus:

• Constante de temps a un ordre de croissance1, par exemple:a = b + c.

• Le temps logarithmique a un ordre de croissanceLogN, il se produit généralement lorsque vous divisez quelque chose en deux (recherche binaire, arbres, même boucles), ou multipliez quelque chose de la même manière.

• Linéaire , l'ordre de croissance estNpar exemple

  int p = 0;
  for (int i = 1; i < N; i++)
    p = p + 2;
  

• Linéaire , l'ordre de croissance estn*logN, se produit généralement dans les algorithmes de division et de conquête.

• Cubique , ordre de croissanceN^3, l'exemple classique est une triple boucle où vous vérifiez tous les triplets:

  int x = 0;
  for (int i = 0; i < N; i++)
     for (int j = 0; j < N; j++)
        for (int k = 0; k < N; k++)
            x = x + 2
  

• L'exponentielle , l'ordre de croissance2^N, se produit généralement lorsque vous effectuez une recherche exhaustive, par exemple, vérifiez des sous-ensembles d'un ensemble.

En gros, la complexité temporelle est un moyen de résumer comment le nombre d'opérations ou d'exécution d'un algorithme augmente à mesure que la taille d'entrée augmente.

Comme la plupart des choses dans la vie, un cocktail peut nous aider à comprendre.

SUR)

Lorsque vous arrivez à la fête, vous devez serrer la main de tout le monde (effectuez une opération sur chaque élément). À mesure que le nombre de participants Naugmente, le temps / travail qu'il vous faudra pour serrer la main de tout le monde augmente au fur et à mesure O(N).

Pourquoi O(N)et non cN?

Il y a des variations dans le temps qu'il faut pour serrer la main des gens. Vous pouvez faire la moyenne de cela et le capturer dans une constante c. Mais l'opération fondamentale ici - serrer la main de tout le monde - serait toujours proportionnelle à O(N), quoi qu'il en csoit. Lorsque nous débattons de l'opportunité d'aller à un cocktail, nous sommes souvent plus intéressés par le fait que nous devrons rencontrer tout le monde que par les moindres détails de l'aspect de ces réunions.

O (N ^ 2)

L'hôte du cocktail veut que vous jouiez à un jeu stupide où tout le monde rencontre tout le monde. Par conséquent, vous devez rencontrer d' N-1autres personnes et, parce que la personne suivante vous a déjà rencontré, elles doivent rencontrer des N-2personnes, etc. La somme de cette série est x^2/2+x/2. Au fur et à mesure que le nombre de participants augmente, le x^2terme devient très rapide , nous abandonnons donc tout le reste.

O (N ^ 3)

Vous devez rencontrer tout le monde et, à chaque réunion, vous devez parler de tout le monde dans la salle.

O (1)

L'hôte veut annoncer quelque chose. Ils sonnent un verre à vin et parlent fort. Tout le monde les entend. Il s'avère que peu importe le nombre de participants, cette opération prend toujours le même temps.

O (log N)

L'hôte a présenté tout le monde à la table par ordre alphabétique. Où est Dan? Vous pensez qu'il doit être quelque part entre Adam et Mandy (certainement pas entre Mandy et Zach!). Compte tenu de cela, est-il entre George et Mandy? Non. Il doit être entre Adam et Fred, et entre Cindy et Fred. Et ainsi de suite ... nous pouvons localiser efficacement Dan en regardant la moitié de l'ensemble, puis la moitié de cet ensemble. En fin de compte, nous regardons les individus O (log_2 N) .

O (N log N)

Vous pouvez trouver où vous asseoir à la table en utilisant l'algorithme ci-dessus. Si un grand nombre de personnes venaient à la table, une à la fois, et toutes le faisaient, cela prendrait du temps O (N log N) . Cela se révèle être le temps qu'il faut pour trier une collection d'articles quand ils doivent être comparés.

Meilleur / pire cas

Vous arrivez à la fête et avez besoin de trouver Inigo - combien de temps cela prendra-t-il? Cela dépend de votre arrivée. Si tout le monde tourne autour, vous avez touché le pire des cas: cela prendra du O(N)temps. Cependant, si tout le monde est assis à la table, cela ne prendra que du O(log N)temps. Ou peut-être pouvez-vous tirer parti du pouvoir de cri de verre à vin de l'hôte et cela ne prendra que du O(1)temps.

En supposant que l'hôte n'est pas disponible, nous pouvons dire que l'algorithme de recherche d'Inigo a une limite inférieure de O(log N)et une limite supérieure de O(N), selon l'état de la fête à votre arrivée.

Espace et communication

Les mêmes idées peuvent être appliquées pour comprendre comment les algorithmes utilisent l'espace ou la communication.

Knuth a écrit un bel article sur l'ancien intitulé "La complexité des chansons" .

Théorème 2: Il existe des chansons arbitrairement longues de complexité O (1).

PREUVE: (due à Casey et au Sunshine Band). Considérez les chansons Sk définies par (15), mais avec

V_k = 'That's the way,' U 'I like it, ' U
U   = 'uh huh,' 'uh huh'

pour tous k.

Je sais que cette question remonte à loin et il y a d'excellentes réponses ici, néanmoins je voulais en partager un autre pour les personnes à l'esprit mathématique qui trébucheront dans ce post. Le théorème maître est une autre chose utile à savoir lors de l'étude de la complexité. Je ne l'ai pas vu mentionné dans les autres réponses.

O (n) est une grande notation O utilisée pour écrire la complexité temporelle d'un algorithme. Lorsque vous additionnez le nombre d'exécutions dans un algorithme, vous obtenez une expression comme résultat 2N + 2, dans cette expression N est le terme dominant (le terme ayant le plus grand effet sur l'expression si sa valeur augmente ou diminue). Or O (N) est la complexité temporelle tandis que N est le terme dominant. Exemple

For i= 1 to n;
  j= 0;
while(j<=n);
  j=j+1;

ici, le nombre total d'exécutions pour la boucle interne est n + 1 et le nombre total d'exécutions pour la boucle externe est n (n + 1) / 2, donc le nombre total d'exécutions pour l'algorithme entier est n + 1 + n (n + 1/2 ) = (n ^ 2 + 3n) / 2. ici n ^ 2 est le terme dominant, donc la complexité temporelle de cet algorithme est O (n ^ 2)