Question Comment trouver la complexité temporelle d'un algorithme


La question

Comment trouver la complexité temporelle d'un algorithme?

Qu'ai-je fait avant de poster une question sur SO?

J'ai traversé ce, ce et de nombreux autres liens

Mais pas où je pouvais trouver une explication claire et simple sur la façon de calculer la complexité du temps.

Qu'est ce que je sais ?

Dire 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; Ceci sera exécuté seulement une fois que. Le temps est réellement calculé pour i=0 et pas la déclaration.

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

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

Donc, le nombre d'opérations requises par cette boucle sont

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

Note: 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 je pense que ces petits calculs de base, mais dans la plupart des cas, j'ai vu la complexité du temps

O (N), O (n2), O (log n), O (n!).... et beaucoup autre,

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


670
2018-06-14 11:21


origine


Réponses:


Comment trouver la complexité temporelle d'un algorithme

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

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

Pourquoi enlevons-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.

Alors le premier terme est 2 millions et le deuxième terme est seulement 2.

Pour cette raison, nous laissons tomber tous les termes, sauf les plus grands, pour le grand N.

Donc, maintenant nous sommes partis de 2N + 2 à 2N.

Traditionnellement, nous ne sommes intéressés que par la performance jusqu'à des facteurs constants.

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

Alors 2N devient juste N.


296
2018-06-14 11:25



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 (au cas où l'excellent lien disparait)

La métrique la plus courante pour calculer la complexité temporelle est la notation Big O. Ceci supprime tous les facteurs constants de sorte que le temps de fonctionnement peut être estimé par rapport à N lorsque N se rapproche de l'infini. En général, vous pouvez penser à 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 se double, le temps de fonctionnement se double également.

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

Est quadratique. Le temps de parcours 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 que 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, l'algorithme est donc une combinaison de logarithmique et de linéaire.

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 la racine cubique, exponentielle et carrée, mais elles ne sont pas aussi courantes. La notation Big O est décrite par O () où est la mesure. L'algorithme quicksort serait décrit comme O (N * log (N)).

Notez que rien de tout cela n'a pris en compte les mesures du meilleur, du pire et du pire. Chacun aurait sa propre notation Big O. Notez également que c'est une explication TRES simpliste. Big O est le plus commun, mais c'est aussi plus complexe que ce que j'ai montré. Il y a aussi d'autres notations telles que le grand oméga, le petit o et le grand thêta. Vous ne les rencontrerez probablement pas en dehors d'un cours d'analyse d'algorithme. ;)


318
2018-01-18 10:04



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

1. Introduction

En informatique, la complexité temporelle d'un algorithme quantifie la durée d'exécution d'un algorithme 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 dite asymptotiquement décrite, c'est-à-dire que 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 de 5n3 + 3n, la complexité du temps asymptotique est O (n3). Plus sur cela plus tard.

Quelques exemples de plus:

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

3. O (1) temps constant:

On dit qu'un algorithme fonctionne en temps constant s'il nécessite la même durée indépendamment de la taille d'entrée.

Exemples:

  • array: accéder à n'importe quel élément
  • pile de taille fixe: méthodes push et pop
  • file d'attente à taille fixe: méthodes enqueue et dequeue

4. O (n) Temps linéaire

Un algorithme est dit fonctionner en temps linéaire si son exécution temporelle est directement proportionnelle à la taille d'entrée, c'est-à-dire que le temps croît linéairement lorsque la taille d'entrée augmente.

Considérons les exemples suivants, ci-dessous je recherche linéairement un élément, ceci 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, Traversée, Trouver minimum etc
  • ArrayList: contient la méthode
  • File d'attente: contient la méthode

5. O (log n) Heure logarithmique:

Un algorithme est dit fonctionner en temps logarithmique si son exécution est proportionnelle au logarithme de la taille d'entrée.

Exemple: Recherche binaire

Rappelez-vous le jeu "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 estimation est trop élevée ou trop basse. Jeu de vingt questions implique une stratégie qui utilise votre nombre deviner pour réduire la taille de l'intervalle de moitié. Voici un exemple de la méthode générale de résolution de problèmes appelée recherche binaire

6. O (n2) Temps quadratique

Un algorithme est dit fonctionner en temps quadratique si son exécution est proportionnelle au carré de la taille d'entrée.

Exemples:

7. Quelques liens utiles


102
2018-03-27 13:14



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

  • Sur): La complexité temporelle d'une boucle est considérée comme Sur) si les variables de boucle sont incrémentées / décrémentées d'un montant constant. Par exemple, les fonctions suivantes ont Sur) la complexité du temps.

    // 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 O (n ^ 2) la complexité du temps

    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 par sélection et le tri par insertion ont O (n ^ 2) la complexité du temps.

  • O (Logn) La complexité temporelle d'une boucle est considérée comme O (Logn) si les variables de 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 O (Logn) la complexité du temps.

  • O (LogLogn) La complexité temporelle d'une boucle est considérée comme O (LogLogn) si les variables de 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
        }
    }    
}

Une 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é totale de temps de l'algorithme ci-dessus est (n + n/2 + n/3 + … + n/n), Qui devient n * (1/1 + 1/2 + 1/3 + … + 1/n)

La chose importante à propos des séries (1/1 + 1/2 + 1/3 + … + 1/n) est égal à O (Logn). Donc, la complexité temporelle du code ci-dessus est O (nLogn).


Ref: 1 2 3


73
2017-11-02 09:31



La complexité du temps avec des exemples

1 - Opérations de base (arithmétique, comparaisons, accès aux éléments du tableau, affectation): Le temps courant 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 - Dans le cas contraire: Ne prendre que le temps maximum d'exécution de deux ou plusieurs déclarations 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 - Boucler (for, while, repeat): Le temps d'exécution de cette instruction est le nombre de boucles multiplié par le nombre d'opérations dans 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).

4 - Boucle imbriquée (looping inside looping): Puisqu'il y a au moins une boucle dans 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 courant

Il existe des 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 course est constant, c'est pas affecté par la taille d'entrée.

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

  3. O (log n) - Heure logarithmique L'algorithme qui a un temps de fonctionnement 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 est souvent trouvé 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 fois. Exemple: Fusionner l'algorithme de tri.

  5. Sur2) - Temps quadratique Look Bubble Sort algorithme!

  6. Sur3) - Temps Cubique Il a le même principe avec O (n2).

  7. O (2n) - Temps exponentiel Il est très lent lorsque l'entrée augmente, si n = 1000.000, T (n) serait 21000.000. L'algorithme Brute Force a ce temps de fonctionnement.

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

Pris à partir de Cet article. Très bien expliqué devrait donner une lecture.


62
2018-04-19 09:36



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 l'additionner pour obtenir une image complète.

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

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

  • Temps constant a un ordre de croissance 1, par exemple: a = b + c.

  • Temps logarithmique a un ordre de croissance LogN, cela se produit généralement quand 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 est N, par exemple

    int p = 0;
    for (int i = 1; i < N; i++)
      p = p + 2;
    
  • Linearithmic, l'ordre de croissance est n*logN, se produit généralement dans les algorithmes de division et de conquête.

  • Cubique, ordre de croissance N^3, 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
    
  • Exponentiel, ordre de croissance 2^N, se produit généralement lorsque vous effectuez une recherche exhaustive, par exemple, vérifiez des sous-ensembles d'un ensemble.


27
2018-06-05 09:43



Autrement dit, la complexité du temps 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)

Quand vous arrivez à la fête, vous devez serrer la main de chacun (faire une opération sur chaque objet). Comme le nombre de participants Naugmente, le temps / travail qu'il vous faudra pour serrer la main de tout le monde augmente O(N).

Pourquoi O(N) et pas cN?

Il y a une variation dans le temps qu'il faut pour serrer la main aux gens. Vous pourriez en faire la moyenne et le capturer dans une constante c. Mais l'opération fondamentale ici - se serrer la main avec tout le monde --- serait toujours proportionnelle à O(N), peu importe ce que c était. Lorsque nous débattons pour savoir si nous devrions aller à un cocktail, nous sommes souvent plus intéressés par le fait que nous devrons rencontrer tout le monde que dans les moindres détails de ce à quoi ressemblent 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 N-1 d'autres personnes et, parce que la prochaine personne vous a déjà rencontré, ils doivent N-2 les gens, et ainsi de suite. La somme de cette série est x^2/2+x/2. Au fur et à mesure que le nombre de participants augmente, x^2 terme devient gros vite, alors on laisse tomber tout le reste.

O (N ^ 3)

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

O (1)

L'hôte veut annoncer quelque chose. Ils ding 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 placé 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!). Compte tenu de cela, est-il entre George et Mandy? 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 O (log_2 N) personnes.

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 tous l'ont fait, cela prendrait O (N log N) temps. Cela se révèle être combien de temps il faut pour trier n'importe quelle collection d'éléments quand ils doivent être comparés.

Meilleur / pire cas

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

En supposant que l'hôte est indisponible, 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), en fonction de l'état de la fête quand vous arrivez.

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 bon article sur l'ancien intitulé "La complexité des chansons".

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

PREUVE: (à cause de Casey et du 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 tout k.


26
2017-10-14 04:12



Je sais que cette question remonte à loin et qu'il y a d'excellentes réponses ici, néanmoins je voulais partager une autre partie pour les gens qui pensent mathématiquement et qui trébucheront dans ce post. le Maître théorème est une autre chose utile à savoir en étudiant la complexité. Je ne l'ai pas vu mentionné dans les autres réponses.


3
2017-11-04 09:20



O (n) est une grosse notation O utilisée pour écrire la complexité temporelle d'un algorithme. Quand vous additionnez le nombre d'exécutions dans un algoritm vous obtiendrez une expression dans le résultat 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). Or O (N) est la comlexité temporelle alors 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 pour cet algorithme est O (n ^ 2)


2
2018-03-11 20:18



Pour avoir une idée d'un algorithme, je le fais souvent expérimentalement. Il suffit de faire varier l'entrée N et de voir combien de temps le calcul prend. Cela nécessite une réflexion, car big-O décrit la complexité de l'algorithme dans le pire des cas, et trouver le pire des cas peut être délicat.

Pour le faire théoriquement, votre approche me semble juste: parcourir le programme (en choisissant toujours le chemin le plus complexe dans le temps), ajouter les temps indiviels et se débarrasser de toutes les constantes / facteurs. Les boucles imbriquées, les sauts, etc. peuvent rendre cela assez complexe, mais je ne peux pas penser à une solution miracle pour résoudre ce problème.

Vous pourriez aussi être interessé dans http://en.wikipedia.org/wiki/Big_O_notation, malgré qu'il soit assez mathématique.

Je viens aussi de trouver http://en.wikipedia.org/wiki/Analysis_of_algorithms


-5
2018-06-14 11:49