Comment trouver la complexité temporelle d'un algorithme

Question

La Question

Comment trouver le temps de la complexité d'un algorithme?

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

Je suis passé par le ce, cet, cette , et beaucoup d'autres liens

Mais pas où j'ai été en mesure de trouver un clair et simple explication de comment calculer le délai de la complexité.

Que sais-je ?

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

Dire 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ée qu' une fois. Le temps est en fait calculée à l' i=0 , et non de la déclaration.

i < N; Ce sera exécutée N+1 fois

i++ ; Ce sera exécutée N fois

Ainsi, le nombre d'opérations nécessaires à cette boucle sont

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

Remarque: Cette encore peut-être tort, comme je ne suis pas confiant quant à ma compréhension sur le calcul de l'heure de la complexité

Ce que je veux savoir ?

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

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

Quelqu'un peut-il m'aider à comprendre comment peut-on calculer le temps de la complexité d'un algorithme? Je suis sûr qu'il ya beaucoup de débutants comme moi de vouloir le savoir.

Merci d'avance

Answer 1

Comment trouver le temps de la complexité d'un algorithme

Vous ajoutez combien d'instructions machine, il va exécuter en fonction de la taille de son entrée, puis simplifier l'expression de la plus grande (lorsque N est très grand) et peut inclure toute la simplification facteur constant.

Par exemple permet de voir comment nous simplifier "2N+2" machine des instructions pour décrire cette "O(N)".:.

Pourquoi ne nous retirez les deux "2"?

Nous nous sommes intéressés à la performance de l'algorithme lorsque N devient grand.

Considérer les deux termes 2N et 2

Quelle est l'influence relative de ces deux termes en tant que N devient grand?

Dire que N est un million de dollars.

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

Pour cette raison, nous baisse tous les, mais le plus grand des termes pour N grand

Alors maintenant, nous avons passé de "2N + 2" à "2N".

Traditionnellement, nous nous intéressons uniquement à la performance "jusqu'à des facteurs constants".

Cela signifie que nous n'avons pas vraiment si il y a constamment un multiple de différence dans les performances lorsque N est grand. L'unité de 2N n'est pas bien défini, en premier lieu, de toute façon. Donc on peut multiplier ou diviser par un facteur constant pour arriver à la plus simple expression.

Donc "2N" n'est qu'un "N".

Stanford (l'un des meilleurs CS écoles sur la planète) est le point de commencer un cours gratuit en ligne sur l'analyse d'algorithmes, je suggère, si vous êtes intéressé à vous joindre à ce cours:

https://www.coursera.org/course/algo

Inscrivez est encore ouvert pour quelques jours.

Answer 2

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

Ci-dessous la réponse est copié à partir de ci-dessus (dans le cas de l'excellent lien va buste)

La plupart de mesure commune pour le calcul de l'heure de la complexité est O la notation. Cela supprime tous les facteurs constants, de sorte que le temps d'exécution peut être estimée par rapport à N N approche de l'infini. En général, vous pouvez la considérer comme ceci:

statement;

Est constante. Le temps d'exécution de l'instruction ne changera pas par rapport à N.

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

Est linéaire. Le temps d'exécution de la boucle est directement proportionnelle à N. Lorsque N est doublé, de sorte que le temps d'exécution.

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

Est quadratique. Le temps d'exécution des deux boucles est proportionnelle au carré de N. Lorsque N est doublé, le temps d'exécution 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 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 );
}

N * log ( N ). Le temps d'exécution est constitué de N en boucle (itératif ou récursif) qui sont logarithmique, donc l'algorithme est une combinaison linéaire et logarithmique.

En général, faire quelque chose avec chaque élément dans une dimension linéaire, de faire quelque chose avec chaque élément en deux dimensions est quadratique, et en divisant la zone de travail dans la moitié est logarithmique. Il y a d'autres Big O des mesures telles que des cubes, exponentielle, et de la racine carrée, mais ils ne sont pas aussi commun. Big O la notation est décrit comme O ( ) où est la mesure. L'algorithme quicksort serait décrit comme O ( N * log ( N ) ).

Notez que rien de cela n'a pris en compte le mieux, en moyenne, et les pires mesures. Chacun aurait son propre Big O la notation. Notez également que c'est une TRÈS explication simpliste. Big O est le plus commun, mais il est aussi plus complexe que j'ai montré. Il y a aussi d'autres notations telles que big omega, peu de o, et de grands thêta. Vous n'aurez probablement pas à les rencontrer à l'extérieur d'un algorithme d'analyse en cours. ;)

Answer 3

Prises à partir d'ici - Introduction à la Complexité temporelle d'un Algorithme

1. Introduction

En informatique, la complexité temporelle d'un algorithme permet de quantifier la quantité de temps pris par un algorithme à exécuter en fonction de la longueur de la chaîne de caractères représentant l'entrée.

2. La notation grand O

La complexité temporelle d'un algorithme est souvent exprimée à l'aide de big O la notation, ce qui exclut les coefficients d'ordre inférieur termes. Lorsqu'elle est exprimée de cette façon, la complexité du temps est dit être décrit à l'infini, c'est à dire, comme la taille de l'image à l'infini.

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

Quelques Exemples:

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

3. O(1) Constante De Temps:

Un algorithme est dit pour s'exécuter en temps constant si elle nécessite la même quantité de temps, indépendamment de la taille de saisie.

Exemples:

• tableau: l'accès à tout élément
• fixe la taille de la pile: push et pop méthodes
• fixe la taille de la file d'attente: mettre en file d'attente et de résorption de l'méthodes

4. O(n) en Temps Linéaire

Un algorithme est dit que dans le temps linéaire si son temps d'exécution est directement proportionnelle à la taille de saisie, c'est à dire le temps augmente de manière linéaire avec la taille de l'image augmente.

Considérons les exemples suivants, ci-dessous je suis linéairement à la recherche 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;
    }
}

D'Autres Exemples:

• Tableau: la Recherche Linéaire, Traversant, Trouver le minimum etc
• Liste de tableaux: contient de la méthode
• File d'attente: contient de la méthode

5. O(log n) Temps Logarithmique:

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

Exemple: Recherche Binaire

Rappelez-vous les "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. Une vingtaine de questions jeu implique une stratégie qui utilise votre de deviner les numéros de réduire de moitié l'intervalle de taille. Ceci est un exemple de la problématique générale de résolution de méthode connue sous le nom de recherche binaire

6. O(n2) Quadratique du Temps

Un algorithme est dit dans quadratique du temps si son temps d'exécution est proportionnel au carré de la taille de saisie.

Exemples:

• Tri À Bulles
• Tri De La Sélection
• Le Tri Par Insertion

7. Certains liens Utiles

• Big-O Les Idées Fausses
• La Détermination De La Complexité De L'Algorithme
• Big O Feuille De Triche

Answer 4

Le temps de la complexité avec des exemples

1 - les Opérations de Base (arithmétique, de comparaisons, d'accéder aux éléments du tableau, l'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 - 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 pseudo-code ci-dessus est T(n) = 2 + 1 + max(1, 1+2) = 6. Ainsi, son grand-oh est toujours constante T(n) = O(1).

3 - Boucle (for, while, repeat): temps d'Exécution de 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é T(n) = 1+4n+1 = 4n + 2. Ainsi, T(n) = O(n).

4 - Nested Loop (boucle à l'intérieur de boucle): Puisqu'il y a 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;

Temps D'Exécution Commun

Il y a beaucoup de temps d'exécution lors de l'analyse d'un algorithme:

1. O(1) – Constante De Temps La constante de temps signifie que le temps d'exécution est constante, il n'est pas affecté par la taille de saisie.

2. O(log n) – échelle Logarithmique de Temps Algorithme fonctionnant en temps 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: binaire de l'algorithme de recherche binaire algorithme de conversion.

3. O(n) – Linéaire dans le Temps Quand un algorithme accepte n la taille de l'image, il réalisera de n opérations.

4. O(n log n) – Linearithmic Temps Ce temps d'exécution est souvent trouvé dans "divide & conquer algorithmes de" diviser le problème en sous problèmes de manière récursive, puis de les fusionner en n temps. Exemple: Fusion algorithme de Tri.

5. O(n^2) – Quadratique du Temps Regarder algorithme de Tri Bubble!

6. O(n^3) – Cubes de Temps Il a le même principe avec O(n^2).

7. O(2^n) – Temps Exponentiel Il est très lent en entrée sont de plus en plus, si n = 1000.000, T(n) serait 21000.000. La Force Brute de l'algorithme a ce temps d'exécution.

8. O(n!) – Factorielle Temps LE PLUS LENT !!! Exemple : les Voyages Problème de voyageur de commerce (TSP)

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

Answer 5

O(n) est O notation utilisée pour l'écriture de la complexité temporelle 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 le temps comlexity tout N est dominant terme. Exemple

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

ici, nombre total de prisonniers à l'intérieur de la boucle sont n+1 et le nombre total d'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 de sorte que le temps de la complexité de cet algorithme est O(n^2)