913 votes

Big O, comment calculez-vous/approximatif?

La plupart des gens avec un diplôme en CS savez certainement ce que Big O est synonyme de. Il nous aide à mesurer le degré de (in)efficace, un algorithme est vraiment et si vous savez dans quelle catégorie le problème que vous essayez de résoudre réside dans , que vous pouvez découvrir si il est encore possible de faire sortir le petit plus de performance.1

Mais je suis curieux, comment vous calculer ou approximative de la complexité des algorithmes?

1mais comme ils le disent, n'en abusez pas, l'optimisation prématurée est la racine de tous les maux, et l'optimisation sans cause justifiée faut mériter ce nom.

1501voto

vz0 Points 11605

Je suis un professeur assistant à mon local de l'université sur les Structures de Données et Algorithmes de parcours. Je vais faire de mon mieux pour l'expliquer ici sur des termes simples, mais sachez que ce sujet prend mes élèves une couple de mois pour enfin comprendre. Vous pouvez trouver plus d'informations sur le Chapitre 2 de l' Structures de Données et Algorithmes en Java livre.

Il n'existe pas de procédure mécanique qui peut être utilisé pour obtenir le BigOh.

Comme un "livre de cuisine", afin d'obtenir la BigOh à partir d'un morceau de code, vous devez d'abord réaliser que vous êtes la création d'une formule math pour compter le nombre d'étapes de calculs exécutés donné une entrée de taille.

Le but est simple: pour comparer les algorithmes à partir d'un point de vue théorique, sans la nécessité d'exécuter le code. Le moindre le nombre d'étapes, le plus rapide de l'algorithme.

Par exemple, disons que vous avez ce morceau de code:

int sum(int* data, int N) {
    int result = 0; // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i]; // 3
    }

    return result; // 4
}

Cette fonction retourne la somme de tous les éléments de la matrice, et nous voulons créer une formule pour compter le calcul de la complexité de cette fonction:

Number_Of_Steps = f(N)

Nous avons donc f(N), une fonction pour compter le nombre d'étapes de calcul. L'entrée de la fonction est la taille de la structure à traiter. Cela signifie que cette fonction est appelée suchs:

Number_Of_Steps = f(data.length)

Le paramètre N prend l' data.length de la valeur. Maintenant, nous avons besoin de la définition de la fonction f(). Ceci est fait à partir du code source, dans lequel chaque intéressants en ligne est numérotée de 1 à 4.

Il existe de nombreuses façons de calculer la BigOh. À partir de ce point, nous allons supposer que chaque phrase qui ne dépend pas de la taille de l'entrée de données prend une constante C nombre de calcul des mesures.

Nous allons ajouter le numéro individuel de mesures de la fonction, ni la déclaration de variable locale, ni l'instruction de retour dépend de la taille de l' data tableau.

Cela signifie que les lignes 1 et 4 prend C nombre de mesures de chaque, et la fonction est un peu comme ceci:

f(N) = C + ??? + C

La prochaine partie consiste à définir la valeur de l' for déclaration. Rappelez-vous que l'on compte le nombre d'étapes de calcul, ce qui signifie que le corps de la déclaration est exécutée N fois. C'est le même que l'ajout d' C, N fois:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

Il n'y a pas de règle qui permet de compter combien de fois le corps de la est exécuté, il vous faudra compter en regardant ce que fait le code. Pour simplifier les calculs, nous ignorons l'initialisation d'une variable, l'état et l'incrément de parties de l' for déclaration.

Pour obtenir le véritable BigOh nous avons besoin de l' analyse Asymptotique de la fonction. C'est à peu près comme ceci:

  1. Emporter tous les constantes C.
  2. D' f() obtenir le polynomium dans ses standard form.
  3. Diviser les termes de la polynomium et de les trier par le taux de croissance.
  4. Garder celui qui prend de l'ampleur lorsqu' N approches infinity.

Notre f() a deux conditions:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Emportant tous l' C des constantes et des parties redondantes:

f(N) = 1 + N ^ 1

Depuis le dernier terme est celui qui pousse le plus grand lorsque l' f() approche de l'infini (réfléchir sur les limites) c'est le BigOh argument, et l' sum() de la fonction de la BigOh de:

O(N)

Il y a quelques astuces pour résoudre des problèmes: l'utilisation des sommes à chaque fois que vous le pouvez. Il y a un peu de pratique , la sommation des identités déjà avéré être correct.

Comme autre exemple, ce code peut être facilement résolu en utilisant des sommations:

// A
for (i = 0; i < 2*n; i += 2) { // 1
    for (j=n; j > i; j--) { // 2
        foo(); // 3
    }
}

La première chose que vous besoin d'être posée est de l'ordre de l'exécution de l' foo(). Alors que l'habitude est O(1), vous devez demander à vos professeurs à ce sujet. O(1) moyen (ou presque, la plupart du temps) constante C, indépendamment de la taille de l' N.

L' for déclaration sur le nombre de phrase est délicat. Alors que l'indice se termine à l' 2 * N, l'accroissement se fait par deux. Cela signifie que la première for est exécuté seulement N étapes, et nous avons besoin de diviser le nombre par deux.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

La phrase numéro deux est encore plus difficile car il dépend de la valeur de i. Prendre un coup d'oeil: l'indice i prend les valeurs: 0, 2, 4, 6, 8, ..., 2 * N, et la secondth for exécutée: N fois la première, N - 2 le secondth, N - 4 le troisième... jusqu'à la N / 2 scène, sur laquelle le secondth for n'est jamais exécutée.

Sur la formule, ce qui signifie:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

Encore une fois, nous comptons le nombre d'étapes. Et par définition, toute somme doit toujours commencer par une, et à la fin à un nombre plus grand ou égal à un.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(Nous supposons qu' foo() est O(1) et prend en C étapes).

Nous avons un problème ici: quand i prend la valeur N / 2 + 1 vers le haut, à l'intérieur de Sommation se termine à un nombre négatif! C'est impossible et le mal. Nous avons besoin de diviser la somme en deux, étant le point central le moment, i faut N / 2 + 1.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

Depuis le moment charnière de l' i > N / 2, l'intérieur pour ne pas exécutée, et nous supposons une constante C de l'exécution de la complexité, de son corps.

Maintenant, les sommations peut être simplifiée en utilisant certaines règles d'identité:

  1. Sommation(w de 1 à N)( C ) = N * C
  2. Sommation(w de 1 à N)( A (+/-) B ) = Somme(w de 1 à N)( A ) (+/-) Somme(w de 1 à N)( B )
  3. Sommation(w de 1 à N)( w * C ) = C * Sommation(w de 1 à N)( w ) (C est une constante, indépendante de l' w)
  4. Sommation(w de 1 à N)( w ) = (w * (w + 1)) / 2

L'application à l'algèbre:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

Et le BigOh est:

O(N ^ 2)

205voto

DShook Points 5361

Big O donne la limite supérieure pour le temps de la complexité d'un algorithme. Il est généralement utilisé en conjonction avec le traitement des séries de données (listes), mais peut être utilisé ailleurs.

Quelques exemples de la façon dont il est utilisé dans le code C.

Dire que nous avons un tableau de n éléments

int array[n];

Si nous voulions pour accéder au premier élément du tableau ce serait O(1), car elle n'a pas d'importance comment grand le tableau, il prend toujours la même constante de temps pour obtenir le premier élément.

x = array[0];

Si nous voulions trouver un numéro dans la liste:

for(int i = 0; i < n; i++){

Ce serait O(n) car nous devons regarder à travers l'ensemble de la liste pour trouver notre numéro. Le Big-O est toujours en O(n), même si nous pourrions trouver notre numéro du premier coup et courir à travers la boucle une fois parce que les Grands-O décrit la limite supérieure pour un algorithme (omega est pour la limite inférieure et thêta est serré lié).

Quand nous arrivons à boucles imbriquées:


Ce est O(n^2), car à chaque passage de la boucle externe ( O(n) ), nous devons aller par le biais de l'ensemble de la liste de nouveau de sorte que le n de se multiplier, nous laissant avec n au carré.

C'est à peine de gratter la surface, mais quand vous arrivez à l'analyse plus complexe des algorithmes mathématiques complexes impliquant des preuves entre en jeu. Espérons que cela aide à vous familiariser avec les notions de base au moins.

97voto

Giovanni Galbo Points 8139

Tout en sachant comment comprendre le Big O moment pour votre problème particulier est utile, sachant que certains cas peuvent aller un long chemin en vous aidant à prendre des décisions dans votre algorithme.

Ici sont quelques-uns des cas les plus courants, levée de http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O(1) - Déterminer si un nombre est pair ou impair; l'utilisation d'une taille constante recherche de table ou table de hachage

O(logn) - la recherche d'un élément dans un tableau trié avec une recherche binaire

O(n) - la recherche d'un élément dans une liste non triée; l'ajout de deux n-chiffres

O(n^2) - Multiplication de deux n-chiffres par un algorithme simple; l'ajout de deux n×n matrices; tri à bulles ou le tri par insertion

O(n^3) - Multiplication de deux n×n matrices par un algorithme simple

O(c^n) - Trouver la (les) solution du problème du voyageur de commerce à l'aide de la programmation dynamique; déterminer si deux instructions logiques sont équivalentes en utilisant la force brute

O(n!) - Résoudre le problème du voyageur de commerce via la recherche par force brute

O(n^n) - Souvent utilisé au lieu de O(n!) pour dériver des formules plus simples pour asymptotique de la complexité

43voto

OysterD Points 2698

Petit rappel: le "big O" est utilisé pour désigner asymptotique de la complexité (qui est, lorsque la taille du problème augmente à l'infini), et il cache une constante.

Cela signifie qu'entre un algorithme en O(n) et une en O(n^2), de la manière la plus rapide n'est pas toujours le premier (bien qu'il existe toujours une valeur de n telle que pour des problèmes de taille >n, le premier algorithme est plus rapide).

Notez que le caché de la constante dépend très largement de la mise en œuvre!

Aussi, dans certains cas, l'exécution n'est pas une fonction déterministe de la "taille" n de l'entrée. Prendre le tri à l'aide de quicksort par exemple: le temps nécessaire pour trier un tableau de n éléments n'est pas une constante mais dépend de la configuration de départ de la matrice; il y a des temps différents complexité: le pire cas (généralement le plus simple à comprendre, mais pas toujours très significatif), moyen (généralement beaucoup plus difficile à déterminer :-( ).

Une bonne introduction est "Une Introduction à l'Analyse des Algorithmes' par R. Sedgewick et P. Flajolet.

Comme vous le dites, "l'optimisation prématurée est la racine de tous les maux" ... et (si possible) de profilage vraiment devrait toujours être utilisé lors de l'optimisation de code. Il peut même vous aider à déterminer la complexité des algorithmes.

27voto

Marcelo Cantos Points 91211

Si votre coût est un polynôme, il suffit de garder le plus élevé-de l'ordre à terme, en l'absence de son multiplicateur. E. g.:

O((n/2 + 1)*(n/2)) = O(n2/4 + n/2) = O(n2/4) = O(n2)

Cela ne fonctionne pas pour les séries infinies, vous l'esprit. Il n'y a pas de recette unique pour le cas général, même si, pour certains cas courants, les inégalités suivantes s'appliquent:

O(log N) < O(N) < O(N log N) < O(N2) < O(Nk) < S(en) < O(n!)

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X