Comment trouver le temps complexité d'un algorithme

La Question

Comment trouver la complexité temporelle d'un algorithme?

Qu'ai-je fait avant de poster une question à ce sujet ?

j'ai vécu ce , ce et beaucoup d'autres liens à

mais non où j'ai pu trouver une explication claire et directe pour calculer le temps complexité.

Qu'est-ce que j'en sais ?

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

pour une boucle comme celle ci-dessous:

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

int i=0; ce sera exécuté seulement une fois . Le temps est en fait calculé à i=0 et non la déclaration.

i < N; Ce sera exécuté N+1 times

i++; ce sera exécuté N times

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

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

Note: Ceci peut encore être erroné, car je ne suis pas sûr de ma compréhension sur le calcul de la complexité du temps

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 beaucoup autres ,

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

690
demandé sur Kushal 2012-06-14 15:21:15
la source

9 ответов

comment trouver la complexité temporelle d'un algorithme

vous additionnez combien d'instructions machine il exécutera en fonction de la taille de son entrée, puis simplifiez l'expression au plus grand (quand N est très grand) terme et peut inclure n'importe quel facteur constant simplifiant.

par exemple, voyons comment nous simplifions les instructions de la machine 2N + 2 pour décrire cela simplement comme O(N) .

pourquoi supprimer les deux 2 s ?

nous sommes intéressés par la performance de l'algorithme que N devient grand.

Considérer les deux termes 2N et 2.

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

alors le premier terme est de 2 millions et le second terme est seulement 2.

pour ce raison, nous tombons tous, mais le plus grand des termes pour les grandes N.

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

traditionnellement, nous ne nous intéressons qu'à la performance jusqu'à des facteurs constants .

cela signifie que nous ne nous soucions pas vraiment s'il y a un multiple constant de différence dans la performance quand N est grand. L'Unité de 2N n'est pas bien définie en premier lieu de toute façon. Afin que nous puissions multiplier ou diviser par un facteur constant pour arriver à la plus simple expression.

ainsi 2N devient juste N .

304
répondu Andrew Tomazos 2017-03-29 14:43:16
la source

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. ;)

329
répondu Achow 2013-01-18 14:04:35
la source

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 3 + 3n, la complexité asymptotique du temps est O(N 3 ). Plus sur cela plus tard.

quelques autres exemples:

  • 1 = O(n)
  • n = O(n 2 )
  • 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:

7. Quelques liens utiles

107
répondu Yasser 2017-06-01 17:29:36
la source

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

74
répondu zangw 2015-11-02 12:31:56
la source

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 2 ) – temps quadratique Algorithme de tri des bulles!

  • O (N 3 ) - temps Cube Il a le même principe avec O (N 2 ).

  • O (2 n ) - 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.

    63
    répondu Yasser 2015-02-25 17:33:13
    la source

    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.

    29
    répondu Aleksandar Makragić 2017-06-17 10:21:13
    la source

    grossièrement parlant, la complexité du temps est une façon de résumer comment le nombre d'opérations ou le temps d'exécution d'un algorithme augmente avec la taille de l'entrée.

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

    O(N)

    quand vous arrivez à la fête, vous devez serrer la main de tout le monde (faire une opération sur chaque élément). Comme le nombre de participants N augmente, le temps/Travail qu'il vous faudra pour serrer la main de tout le monde augmente comme O(N) .

    pourquoi O(N) et pas cN ?

    il y a une variation dans le temps qu'il faut pour serrer la main des gens. Vous pouvez faire la moyenne de ceci et le capturer dans une constante c . Mais l'opération fondamentale ici --- serrer la main de tout le monde --- sera toujours proportionnelle à O(N) , peu importe ce qu'était c . Lorsque nous débattons pour savoir si nous devrions aller à un cocktail, nous sommes souvent plus intéressés par le fait que nous aurons à rencontrer tout le monde que dans les moindres détails de ce que ces réunions ressemblent.

    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 N-1 d'autres personnes et, parce que la prochaine personne a déjà vous rencontrer, ils doivent rencontrer des gens N-2 , et ainsi de suite. La somme de cette série est x^2/2+x/2 . Comme le nombre de participants augmente , le x^2 terme devient grand rapide , donc nous laissons tomber tout le reste.

    O (N^3)

    vous devez rencontrer tout le monde et, pendant 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 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 mis tout le monde à la table dans l'ordre alphabétique. Où est Dan? Vous pensez qu'il doit être quelque part entre Adam et Mandy (certainement pas entre Mandy et Zach!). Il est entre George et Mandy? Aucun. 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 et puis la moitié de cet ensemble. En fin de compte, nous examinons les personnes 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 les gens sont venus à la table, un à la fois, et tous ont fait cela, qui prendrait O(N log n) temps. Cela s'avère être combien de temps il faut pour trier une collection d'éléments lorsqu'ils doivent être comparées.

    Le Meilleur/Pire Des Cas

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

    en supposant que l'hôte n'est pas disponible, nous pouvons dire que L'algorithme de recherche Inigo a une limite inférieure de O(log N) et une limite supérieure de O(N) , selon l'état de la partie quand vous arrivez.

    Espace & 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 beau papier sur le premier intitulé "la complexité des chansons" .

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

    preuve: (due to Casey and the Sunshine Band). Considérez les chansons Sk défini par (15), mais avec

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

    pour tout k.

    27
    répondu Richard 2015-10-14 07:12:28
    la source

    je sais que cette question remonte à loin et il y a d'excellentes réponses ici, néanmoins je voulais partager un autre peu pour les gens mathématiquement-pensants qui vont trébucher dans ce post. Le Master theorem est une autre chose utile à savoir en étudiant la complexité. Je ne l'ai pas vu mentionné dans les autres réponses.

    3
    répondu Gentian Kasa 2015-11-04 12:20:14
    la source

    O (n) est une grande notation O utilisée pour écrire la complexité du temps d'un algorithme. Lorsque vous additionnez le nombre d'exécutions dans un algorithme, vous obtiendrez une expression de la conséquence comme 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). Maintenant O (N) est la comlexité temporelle tandis que N domine le terme. Exemple

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

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

    2
    répondu ifra khan 2013-03-12 00:18:39
    la source