Comment trouver le temps complexité d'un algorithme

c'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 (dans le cas où l'excellent lien va buste)

la métrique la plus courante pour calculer la complexité du temps est la notation Big O. Cela supprime tous les facteurs constants de sorte que la durée de fonctionnement peut être estimée par rapport à N comme n approche de l'infini. En général, vous pouvez le penser comme ceci:

statement;

est constant. La durée de la déclaration ne changera pas par rapport à N.

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

est linéaire. Le temps de fonctionnement de la boucle est directement proportionnel à N. lorsque N double, il en va de même du temps de fonctionnement.

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. augmentation du temps de fonctionnement de N * n * 151980920"

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 proportionnelle au nombre de fois que N peut être divisé par 2. C'est parce que l'algorithme divise la zone de travail de moitié à 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 se compose de n boucles (itératives ou récursives) qui sont logarithmiques, donc l'algorithme est une combinaison de linéaire et 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 y a d'autres mesures de Grand O comme cubique, exponentielle et racine carrée, mais elles ne sont pas aussi courantes. La notation Big O est décrite comme O () où est la mesure. L'algorithme de quicksort serait décrit comme O ( N * log (N ) ).

notez que rien de tout cela n'a prise en compte des mesures les meilleures, moyennes et les pires. Chacune aurait sa propre notation Big O. Notez également qu'il s'agit d'une explication très simpliste. Big O est le plus commun, mais c'est aussi plus complexe que j'ai montré. Il y a aussi d'autres notations comme big omega, little o, et big theta. Vous ne les rencontrerez probablement pas en dehors d'un cours d'analyse d'algorithme. ;)

tiré d'ici - introduction à la complexité temporelle d'un algorithme

1. Introduction

en informatique, la complexité temporelle d'un algorithme quantifie le temps pris par un algorithme pour fonctionner 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 grand O notation, qui exclut les coefficients et les Termes d'ordre inférieur. Lorsque exprimé de cette façon, la complexité du temps est dit être décrit asymptotiquement, i.e., comme la taille d'entrée va à l'infini.

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

quelques autres exemples:

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

3. O (1) Temps Constant:

un algorithme est dit exécuté en temps constant s'il nécessite le même temps, quelle que soit la taille de l'entrée.

exemples:

• tableau: l'accès à toute élément
• stack fixe-size: push and pop methods
• fixe la taille de la file d'attente: mettre en file d'attente et de résorption de l'méthodes

4. O (n )temps linéaire

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

considérez les exemples suivants, ci-dessous je suis à la recherche linéaire d'un élément, ce qui a une complexité temporelle en 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;
    }
}

Autres Exemples:

• Tableau: la Recherche Linéaire, Traversant, Trouver le minimum etc
• ArrayList: contient la méthode
• file: contains method

5. O (log n) Temps logarithmique:

Un algorithme est dit en temps logarithmique si son temps d'exécution est proportionnel à la logarithme de la taille de saisie.

Exemple: Recherche Binaire

Rappel "vingt questions" jeu de la tâche est de deviner la valeur d'un nombre caché dans un intervalle. Chaque fois que vous faites une supposition, on vous dit si votre proposition est trop basse ou trop haute. Vingt questions jeu implique une stratégie qui utilise votre nombre de conjectures 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 (n2) temps quadratique

un algorithme est dit exécuté en temps quadratique si son exécution en temps est proportionnelle au carré de la taille de l'entrée.

exemples:

• Sélection
• Insertion Tri

7. Quelques liens utiles

• Big-O Misconceptions
• Détermination De La Complexité De L'Algorithme
• Big O Feuille De Triche

bien qu'il y ait de bonnes réponses à cette question. Je voudrais donner une autre réponse ici 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'un montant constant. Par exemple, les fonctions suivantes ont O(n) complexité temporelle.

  // 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 interne est exécutée. Par exemple, les boucles d'échantillon suivantes ont O (N^2) complexité temporelle

  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 tri de sélection et Tri D'Insertion ont O(N^2) complexité temporelle.

• 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 un montant 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
  }
  

  par exemple recherche binaire a O(Logn) complexité de temps.

• O(LogLogn) la complexité temporelle d'une boucle est considérée comme O(LogLogn) si la boucle les variables sont réduites / augmentées exponentiellement par un montant constant.

  // 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 la complexité du temps

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.

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

le chose importante au sujet de la série (1/1 + 1/2 + 1/3 + … + 1/n) est égal à O(Logn) . Ainsi, la complexité temporelle du code ci-dessus est O(nLogn) .

---

Ref: 1 2 3

complexité temporelle avec exemples

1-opérations de base ( arithmétique, comparaisons, accès aux éléments du tableau, assignation): le temps de fonctionnement 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 - Si alors sinon énoncé: que de prendre le maximum de temps d'exécution à partir de deux ou plusieurs états 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é de la ci-dessus le pseudo-code est T (n) = 2 + 1 + max(1, 1+2) = 6. Ainsi, son grand oh est toujours constant T(n) = O (1).

3-boucle (for, while, repeat): le temps D'exécution pour cette instruction est le nombre de boucle 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

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

boucle à 4 emboîtements (boucle intérieure bouclée): depuis là au moins une boucle à l'intérieur de la boucle principale, temps d'exécution de cette instruction utilisée 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;

"151940920 Commune" Temps D'Exécution

il y a des temps d'exécution communs lors de l'analyse d'un algorithme:

"1519300920 –

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

O(n) – temps linéaire Quand un algorithme accepte n Taille d'entrée, il effectuerait n opérations aussi bien.

O(log n) – Temps logarithmique L'algorithme 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 avec la même taille. Exemple: algorithme de recherche binaire, algorithme de conversion binaire.

O (N log n) – Linearithmic Temps Ce temps de fonctionnement est souvent trouvé dans "divide & conquer algorithms" qui divisent le problème en sous-problèmes récursivement, puis les fusionner en n temps. Exemple: Fusion algorithme de Tri.

O(N ² ) – temps quadratique Algorithme de tri des bulles!

O (N ³ ) - temps Cube Il a le même principe avec O (N ² ).

O (2 ⁿ ) - temps exponentiel Il est très lent car l'entrée devient plus grande, si n = 1000.000, T(n) serait 21000.000. L'algorithme force Brute a cette durée.

O (N!) – Factorielle Temps LE PLUS LENT !!! Exemple: Travel Salesman Problem (TSP)

tiré de cet article . Très bien expliqué devrait donner à lire.

quand 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 la somme pour obtenir une image complète.

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

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

• le temps Constant a un ordre de croissance 1 , par exemple: a = b + c .

• temps logarithmique a un ordre de croissance LogN , il se produit habituellement quand on divise quelque chose en deux (recherche binaire, arbres, même boucles), ou qu'on multiplie quelque chose de la même façon.

• linéaire , l'ordre de croissance est N , par exemple

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

• Linéarithmique 1519130920" , l'ordre de croissance est n*logN , se produit généralement dans divide and conquer algorithms.

• Cubic , ordre de croissance N^3 , exemple classique est une boucle triple 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
  

• exponentielle , ordre de croissance 2^N , se produit habituellement lorsque vous faites la recherche exhaustive, par exemple vérifier les sous-ensembles d'un ensemble.