Big O, comment calculez-vous / approximez-vous cela?

La plupart des personnes diplômées en CS sauront certainement ce que Big O représente . Cela nous aide à mesurer à quel point un algorithme est réellement efficace et si vous savez dans quelle catégorie se trouve le problème que vous essayez de résoudre, vous pouvez déterminer s’il est encore possible de réduire ce petit surplus de performances. 1

Mais je suis curieux, comment calculez- vous ou approximez-vous la complexité de vos algorithmes?

1 mais comme ils le disent, n’en faites pas trop, l’ optimisation prématurée est la racine de tout mal , et l’optimisation sans cause justifiée devrait également mériter ce nom.

Je suis professeur assistant dans mon université locale sur le cours Structures de données et algorithmes. Je ferai de mon mieux pour l’expliquer ici en termes simples, mais sachez que ce sujet prend quelques mois à mes étudiants pour finalement comprendre. Vous trouverez plus d’informations sur le chapitre 2 du manuel Structures de données et algorithmes dans Java .


Il n’y a pas de procédure mécanique pouvant être utilisée pour obtenir le BigOh.

En tant que “livre de recettes”, pour obtenir le BigOh à partir d’un morceau de code, vous devez d’abord vous rendre compte que vous créez une formule mathématique pour compter le nombre d’étapes de calcul exécutées avec une entrée de taille.

L’objective est simple: comparer des algorithmes d’un sharepoint vue théorique, sans avoir à exécuter le code. Plus le nombre d’étapes est petit, plus l’algorithme est rapide.

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 sum de tous les éléments du tableau, et nous voulons créer une formule pour compter la complexité de calcul 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 correspond à la taille de la structure à traiter. Cela signifie que cette fonction est appelée comme:

 Number_Of_Steps = f(data.length) 

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

Il y a plusieurs façons de calculer le BigOh. À partir de ce moment, nous allons supposer que chaque phrase qui ne dépend pas de la taille des données d'entrée nécessite un nombre constant d'étapes de calcul du nombre C

Nous allons append le nombre individuel d'étapes de la fonction, et ni la déclaration de variable locale ni l'instruction de retour ne dépendent de la taille du tableau de data .

Cela signifie que les lignes 1 et 4 prennent chacune un nombre d’étapes C et que la fonction est un peu comme ceci:

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

La partie suivante consiste à définir la valeur de l'instruction for . Rappelez-vous que nous comptons le nombre d'étapes de calcul, ce qui signifie que le corps de l'instruction for est exécuté N fois. C'est la même chose que d'append des temps C , N :

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

Il n'y a pas de règle mécanique pour compter combien de fois le corps du for est exécuté, vous devez le compter en regardant ce que fait le code. Pour simplifier les calculs, nous ignorons les parties initialisation, condition et incrémentation de la variable for .

Pour obtenir le BigOh actuel, nous avons besoin de l' parsing asymptotique de la fonction. Ceci est grossièrement fait comme ceci:

  1. Enlevez toutes les constantes C
  2. De f() obtenir le polynôme dans sa standard form .
  3. Divisez les termes du polynôme et sortingez-les selon le taux de croissance.
  4. Gardez celui qui grossit quand N s'approche de l' infinity .

Notre f() a deux termes:

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

Enlever toutes les constantes C et les parties redondantes:

 f(N) = 1 + N ^ 1 

Puisque le dernier terme est celui qui grossit quand f() approche de l'infini (pensez aux limites ), c'est l'argument BigOh, et la fonction sum() a un BigOh de:

 O(N) 

Il existe quelques astuces pour résoudre certains problèmes délicats: utilisez des sommations chaque fois que vous le pouvez.

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

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

La première chose à laquelle vous devez répondre est l'ordre d'exécution de foo() . Bien que l’habitude soit d’être O(1) , vous devez en parler à vos professeurs. O(1) signifie (presque) la constante C , indépendante de la taille N

L'énoncé de la phrase numéro un est délicat. Alors que l'index se termine à 2 * N , l'incrément est fait par deux. Cela signifie que le premier for est exécuté seulement N étapes, et nous devons diviser le compte 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 délicate car elle dépend de la valeur de i . Jetez un coup d'oeil: l'index i prend les valeurs: 0, 2, 4, 6, 8, ..., 2 * N, et le second for être exécuté: N fois le premier, N - 2 le second, N - 4 la troisième ... jusqu'à la phase N / 2, sur laquelle la seconde n'est jamais exécutée.

Sur la formule, cela signifie:

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

Encore une fois, nous comptons le nombre d'étapes . Et par définition, chaque sommation doit toujours commencer à un et se terminer par 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 que foo() est O(1) et prend des pas C )

Nous avons un problème ici: quand i prends la valeur N / 2 + 1 vers le haut, la sum interne se termine par un nombre négatif! C'est impossible et faux. Nous devons diviser la sum en deux, étant le point crucial au moment où i prends 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 i > N / 2 , l'interne for ne sera pas exécuté, et nous supposons une complexité d'exécution C constante sur son corps.

Maintenant, les sommations peuvent être simplifiées à l'aide de règles d'identité:

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

Appliquer de 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 c'est:

 O(N²) 

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

Quelques exemples de son utilisation en code C

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

 int array[n]; 

Si nous voulions accéder au premier élément du tableau, il s’agirait de O (1), car la taille du tableau importe peu, cela prend toujours le même temps constant 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++){ if(array[i] == numToFind){ return i; } } 

Ce serait O (n) car tout au plus, nous devrions parcourir toute la liste pour trouver notre numéro. Le Big-O est toujours O (n) même si nous pourrions trouver notre numéro en premier et parcourir la boucle une fois parce que Big-O décrit la limite supérieure d'un algorithme (oméga est pour la limite inférieure et thêta pour la limite) .

Quand on arrive aux boucles nestedes:

 for(int i = 0; i < n; i++){ for(int j = i; j < n; j++){ array[j] += 2; } } 

Ceci est O (n ^ 2) car pour chaque passage de la boucle externe (O (n)), nous devons parcourir à nouveau la liste entière pour que les n se multiplient en nous laissant n au carré.

Cela ne fait que gratter la surface, mais lorsque vous parsingz des algorithmes plus complexes, des mathématiques complexes impliquant des épreuves entrent en jeu. J'espère que cela vous familiarise avec les bases au moins bien.

Bien qu’il soit utile de savoir comment déterminer l’heure de Big O pour votre problème particulier, connaître certains cas généraux peut vous aider à prendre des décisions dans votre algorithme.

Voici quelques-uns des cas les plus courants, tirés de http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions :

O (1) – Déterminer si un nombre est pair ou impair; en utilisant une table de consultation ou une table de hachage de taille constante

O (logn) – Recherche d’un élément dans un tableau sortingé avec une recherche binary

O (n) – Recherche d’un élément dans une liste non sortingée; append deux nombres à n chiffres

O (n 2 ) – Multiplier deux nombres à n chiffres par un algorithme simple; append deux masortingces n × n; sorting par bulles ou sorting par insertion

O (n 3 ) – Multiplication de deux masortingces n × n par un algorithme simple

O (c n ) – Trouver la solution (exacte) au problème du voyageur de commerce en utilisant la programmation dynamic; 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é à la place de O (n!) Pour dériver des formules plus simples pour la complexité asymptotique

Petit rappel: la big O notation big O est utilisée pour désigner la complexité asymptotique (c’est-à-dire lorsque la taille du problème augmente à l’infini) et cache une constante.

Cela signifie qu’entre un algorithme dans O (n) et un dans O (n 2 ), le plus rapide n’est pas toujours le premier (bien qu’il existe toujours une valeur de n telle que pour les problèmes de taille> n, le premier algorithme est le plus rapide).

Notez que la constante cachée dépend beaucoup de l’implémentation!

En outre, dans certains cas, le runtime n’est pas une fonction déterministe de la taille n de l’entrée. Prenez par exemple le sorting rapide: le temps nécessaire pour sortinger un tableau de n éléments n’est pas une constante mais dépend de la configuration de départ du tableau.

Il y a différentes complexités de temps:

  • Le pire des cas (généralement le plus simple à comprendre, mais pas toujours très significatif)
  • Cas moyen (généralement plus difficile à comprendre …)

Une bonne introduction est une introduction à l’parsing des algorithmes par R. Sedgewick et P. Flajolet.

Comme vous le dites, l’ premature optimisation is the root of all evil et, si possible, le profilage doit toujours être utilisé pour optimiser le code. Cela peut même vous aider à déterminer la complexité de vos algorithmes.

En voyant les réponses ici, je pense que nous pouvons en conclure que la plupart d’entre nous s’approchent de l’ordre de l’algorithme en le regardant et en utilisant le bon sens au lieu de le calculer, par exemple, à l’université. Cela dit, je dois append que même le professeur nous a encouragés (plus tard) à y réfléchir au lieu de le calculer.

J’aimerais aussi append comment cela est fait pour les fonctions récursives :

supposons que nous ayons une fonction comme ( code de schéma ):

 (define (fac n) (if (= n 0) 1 (* n (fac (- n 1))))) 

qui calcule de manière récursive la factorielle du nombre donné.

La première étape consiste à essayer de déterminer la caractéristique de performance pour le corps de la fonction uniquement dans ce cas, rien de spécial n’est fait dans le corps, juste une multiplication (ou le retour de la valeur 1).

La performance du corps est donc: O (1) (constante).

Ensuite, essayez de déterminer le nombre d’appels récursifs . Dans ce cas, nous avons n-1 appels récursifs.

La performance pour les appels récursifs est donc la suivante: O (n-1) (l’ordre est n, car nous jetons les parties insignifiantes).

Ensuite, mettez ces deux ensemble et vous aurez alors la performance pour toute la fonction récursive:

1 * (n-1) = O (n)


Peter , pour répondre à vos questions soulevées; la méthode que je décris ici gère bien cela. Mais gardez à l’esprit qu’il s’agit toujours d’une approximation et non d’une réponse mathématiquement correcte. La méthode décrite ici est également l’une des méthodes qui nous ont été enseignées à l’université, et si je me souviens bien, elle a été utilisée pour des algorithmes beaucoup plus avancés que le factoriel utilisé dans cet exemple.
Bien sûr, tout dépend de la manière dont vous pouvez estimer le temps d’exécution du corps de la fonction et le nombre d’appels récursifs, mais c’est tout aussi vrai pour les autres méthodes.

Si votre coût est un polynôme, conservez le terme le plus élevé sans son multiplicateur. Par exemple:

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

Cela ne fonctionne pas pour les séries infinies, remarquez. Il n’y a pas de recette unique pour le cas général, bien que pour certains cas courants, les inégalités suivantes s’appliquent:

O (log N ) N ) N log N ) N 2 ) N k ) n ) n !)

J’y pense en termes d’informations. Tout problème consiste à apprendre un certain nombre de bits.

Votre outil de base est le concept de points de décision et leur entropie. L’entropie d’un sharepoint décision est la moyenne d’informations qu’il vous donnera. Par exemple, si un programme contient un sharepoint décision à deux twigs, son entropie est la sum de la probabilité de chaque twig fois le log 2 de la probabilité inverse de cette twig. C’est ce que vous apprenez en exécutant cette décision.

Par exemple, une instruction if ayant deux twigs, toutes deux également probables, a une entropie de 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Son entropie est donc de 1 bit.

Supposons que vous cherchiez une table de N éléments, comme N = 1024. C’est un problème de 10 bits car log (1024) = 10 bits. Donc, si vous pouvez effectuer une recherche avec des déclarations IF qui ont des résultats tout aussi probables, il convient de prendre 10 décisions.

C’est ce que vous obtenez avec la recherche binary.

Supposons que vous effectuez une recherche linéaire. Vous regardez le premier élément et demandez si c’est celui que vous voulez. Les probabilités sont 1/1024 et 1023/1024 ce n’est pas le cas. L’entropie de cette décision est 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * environ 0 = environ 0,01 bit. Vous avez très peu appris! La deuxième décision n’est pas beaucoup mieux. C’est pourquoi la recherche linéaire est si lente. En fait, le nombre de bits à apprendre est exponentiel.

Supposons que vous effectuez une indexation. Supposons que la table soit pré-sortingée dans un grand nombre de cases et que vous utilisiez une partie de tous les bits de la clé pour indexer directement dans l’entrée de la table. S’il y a 1024 cases, l’entropie est 1/1024 * log (1024) + 1/1024 * log (1024) + … pour tous les 1024 résultats possibles. C’est 1/1024 * 10 fois 1024 résultats, ou 10 bits d’entropie pour cette opération d’indexation. C’est pourquoi la recherche d’indexation est rapide.

Pensez maintenant au sorting. Vous avez N éléments et vous avez une liste. Pour chaque élément, vous devez rechercher l’emplacement de l’élément dans la liste, puis l’append à la liste. Le sorting prend donc environ N fois le nombre d’étapes de la recherche sous-jacente.

Les sortes basées sur des décisions binarys ayant des résultats à peu près également probables prennent toutes en compte les étapes O (N log N). Un algorithme de sorting O (N) est possible s’il est basé sur une recherche par indexation.

J’ai trouvé que presque tous les problèmes de performance algorithmiques peuvent être examinés de cette manière.

Commençons depuis le début.

Tout d’abord, acceptez le principe selon lequel certaines opérations simples sur des données peuvent être effectuées en temps O(1) , c’est-à-dire dans le temps, indépendamment de la taille de l’entrée. Ces opérations primitives en C consistent en

  1. Opérations arithmétiques (par exemple + ou%).
  2. Opérations logiques (par exemple, &&).
  3. Opérations de comparaison (par exemple, < =).
  4. Structure accédant aux opérations (par exemple, indexation de tableaux comme A [i] ou pointeur avec l’opérateur ->).
  5. Affectation simple telle que copier une valeur dans une variable.
  6. Appels aux fonctions de la bibliothèque (par exemple, scanf, printf).

La justification de ce principe nécessite une étude détaillée des instructions machine (étapes primitives) d’un ordinateur type. Chacune des opérations décrites peut être effectuée avec un petit nombre d’instructions de machine; souvent, une ou deux instructions seulement sont nécessaires. En conséquence, plusieurs types d’instructions dans C peuvent être exécutés en temps O(1) , c’est-à-dire dans une quantité de temps constante indépendante de l’entrée. Ces simples comprennent

  1. Instructions d’affectation n’impliquant pas d’appels de fonction dans leurs expressions.
  2. Lire les déclarations.
  3. Écrivez des instructions qui ne nécessitent pas d’appels de fonction pour évaluer les arguments.
  4. Les instructions de sauts brisent, continuent, obtiennent et renvoient l’expression, où l’expression ne contient pas d’appel de fonction.

En C, de nombreuses boucles for sont formées en initialisant une variable d’index à une certaine valeur et en incrémentant cette variable de 1 à chaque fois autour de la boucle. La boucle for se termine lorsque l’index atteint une certaine limite. Par exemple, le for-loop

 for (i = 0; i < n-1; i++) { small = i; for (j = i+1; j < n; j++) if (A[j] < A[small]) small = j; temp = A[small]; A[small] = A[i]; A[i] = temp; } 

utilise la variable d'index i. Il incrémente i de 1 à chaque fois autour de la boucle, et les itérations s'arrêtent lorsque j'atteins n - 1.

Cependant, pour le moment, concentrez-vous sur la forme simple de for-loop, où la différence entre les valeurs finales et initiales, divisée par la quantité d'incrément de la variable d'index, nous indique combien de fois nous faisons le tour de la boucle . Ce compte est exact, sauf s'il existe des moyens de quitter la boucle via un énoncé de saut; c'est une limite supérieure sur le nombre d'itérations dans tous les cas.

Par exemple, la boucle for itère ((n − 1) − 0)/1 = n − 1 times , puisque 0 est la valeur initiale de i, n - 1 est la valeur la plus élevée atteinte par i n-1, la boucle s'arrête et aucune itération ne se produit avec i = n-1), et 1 est ajouté à i à chaque itération de la boucle.

Dans le cas le plus simple, où le temps passé dans le corps de la boucle est le même pour chaque itération, nous pouvons multiplier la limite supérieure du corps entier par le nombre de fois autour de la boucle . Ssortingctement parlant, il faut alors append O (1) le temps pour initialiser l’index de boucle et O (1) le temps pour la première comparaison de l’indice de boucle avec la limite , car nous testons une fois de plus la boucle. Cependant, à moins qu’il soit possible d’exécuter la boucle à zéro, le temps d’initialisation de la boucle et de test de la limite une fois est un terme faible qui peut être supprimé par la règle de sommation.


Considérons maintenant cet exemple:

 (1) for (j = 0; j < n; j++) (2) A[i][j] = 0; 

Nous soaps que la ligne (1) prend O(1) temps. Nous contournons clairement la boucle n fois, comme nous pouvons le déterminer en soustrayant la limite inférieure de la limite supérieure trouvée sur la ligne (1) et en ajoutant ensuite 1. Puisque le corps, ligne (2), prend O (1) temps, on peut négliger le temps d'incrémenter j et le temps de comparer j avec n, qui sont tous deux O (1). Ainsi, le temps d'exécution des lignes (1) et (2) est le produit de n et O (1) , qui est O(n) .

De même, nous pouvons limiter le temps d’exécution de la boucle externe composée des lignes (2) à (4), qui est

 (2) for (i = 0; i < n; i++) (3) for (j = 0; j < n; j++) (4) A[i][j] = 0; 

Nous avons déjà établi que la boucle des lignes (3) et (4) prend O (n) le temps. Ainsi, nous pouvons négliger le temps O (1) pour incrémenter i et tester si i

L'initialisation i = 0 de la boucle externe et le test (n + 1) st de la condition i O(n^2) .


Un exemple plus pratique.

entrer la description de l'image ici

Si vous souhaitez estimer de manière empirique l’ordre de votre code plutôt que d’parsingr le code, vous pouvez coller une série de valeurs croissantes de n et de temps à votre code. Tracez vos timings sur une échelle de log. Si le code est O (x ^ n), les valeurs doivent tomber sur une ligne de pente n.

Cela présente plusieurs avantages par rapport à la simple étude du code. D’une part, vous pouvez voir si vous êtes dans la plage où le temps d’exécution approche son ordre asymptotique. En outre, vous pouvez constater que du code que vous pensiez être de l’ordre O (x) est vraiment de l’ordre O (x ^ 2), par exemple, à cause du temps passé dans les appels de bibliothèque.

Fondamentalement, ce qui revient à 90% du temps, ce n’est qu’parsingr les boucles. Avez-vous des boucles simples, doubles, sortingples? Vous avez O (n), O (n ^ 2), O (n ^ 3) le temps de fonctionnement.

Très rarement (sauf si vous écrivez une plate-forme avec une bibliothèque de base étendue (comme par exemple la BCL .NET ou la STL de C ++), vous rencontrerez tout ce qui est plus difficile que de simplement regarder vos boucles (pour les instructions while, goto, etc…)

Décomposez l’algorithme en morceaux dont vous connaissez la grande notation O et combinez-les par de gros opérateurs O. C’est la seule façon que je connaisse.

Pour plus d’informations, consultez la page Wikipedia sur le sujet.

La notation Big O est utile car elle est facile à utiliser et cache des complications et des détails inutiles (pour une définition des inutiles). La méthode de l’arbre est un bon moyen de comprendre la complexité des algorithmes de division et de conquête. Disons que vous avez une version de quicksort avec la procédure médiane, de sorte que vous divisez le tableau en sous-réseaux parfaitement équilibrés à chaque fois.

Maintenant, construisez un arbre correspondant à tous les tableaux avec lesquels vous travaillez. A la racine, vous avez le tableau d’origine, la racine a deux enfants qui sont les sous-réseaux. Répétez cette opération jusqu’à ce que vous ayez des tableaux d’éléments uniques en bas.

Comme nous pouvons trouver la médiane en O (n) et diviser le tableau en deux parties en O (n), le travail effectué à chaque nœud est O (k) où k est la taille du tableau. Chaque niveau de l’arbre contient (tout au plus) l’ensemble du tableau, le travail par niveau est donc O (n) (la taille des sous-réseaux est de n et nous pouvons append ceci puisque nous avons O (k) par niveau) . Il n’ya que des niveaux de log (n) dans l’arbre, car chaque fois que nous divisons par deux l’entrée.

Nous pouvons donc limiter la quantité de travail par O (n * log (n)).

Cependant, Big O cache des détails que nous ne pouvons parfois pas ignorer. Envisager de calculer la séquence de Fibonacci avec

 a=0; b=1; for (i = 0; i  

et supposons juste que les a et b sont des BigIntegers en Java ou quelque chose qui peut gérer des nombres arbitrairement grands. La plupart des gens diraient que c'est un algorithme O (n) sans broncher. Le raisonnement est que vous avez n itérations dans la boucle for et O (1) dans la boucle.

Mais les nombres de Fibonacci sont grands, le nième nombre de Fibonacci est exponentiel en n, donc il suffit de le stocker dans l'ordre de n octets. Effectuer l'addition avec de gros nombres entiers nécessitera une quantité de travail O (n). Ainsi, la quantité totale de travail effectuée dans cette procédure est

1 + 2 + 3 + ... + n = n (n-1) / 2 = O (n ^ 2)

Donc, cet algorithme fonctionne en temps quadruple!

Connaissance des algorithmes / structures de données que j’utilise et / ou parsing rapide de l’imbrication des itérations. La difficulté est lorsque vous appelez une fonction de bibliothèque, éventuellement plusieurs fois – vous pouvez souvent ne pas savoir si vous appelez la fonction inutilement à certains moments ou quelle implémentation elle utilise. Les fonctions de bibliothèque devraient peut-être comporter une mesure de complexité / efficacité, que ce soit Big O ou une autre mesure, disponible dans la documentation ou même IntelliSense .

Moins utile en général, je pense, mais pour être complet, il y a aussi un Big Omega Ω , qui définit une limite inférieure de la complexité d’un algorithme, et un Big Theta Θ , qui définit à la fois une limite supérieure et inférieure.

Quant à “comment calculez-vous” Big O, cela fait partie de la théorie de la complexité informatique . Pour certains (nombreux) cas particuliers, vous pouvez être en mesure d’apporter des heuristiques simples (comme multiplier le nombre de boucles pour les boucles nestedes), notamment. lorsque tout ce que vous voulez, c’est une estimation supérieure, et cela ne vous dérange pas si c’est trop pessimiste – ce qui, je suppose, concerne probablement votre question.

Si vous voulez vraiment répondre à votre question pour n’importe quel algorithme, le mieux que vous puissiez faire est d’appliquer la théorie. En plus de l’parsing simpliste des cas les plus défavorables, j’ai trouvé que l’ parsing amortie était très utile dans la pratique.

Pour le 1er cas, la boucle interne est exécutée ni fois, donc le nombre total d’exécutions est la sum de i allant de 0 à n-1 (parce que inférieure à, pas inférieure ou égale) du ni . Vous obtenez finalement n*(n + 1) / 2 , donc O(n²/2) = O(n²) .

Pour la 2ème boucle, i est compris entre 0 et n inclus pour la boucle externe; alors la boucle interne est exécutée lorsque j est ssortingctement supérieur à n , ce qui est alors impossible.

En plus d’utiliser la méthode maître (ou l’une de ses spécialisations), je teste mes algorithmes expérimentalement. Cela ne peut pas prouver qu’une classe de complexité particulière est atteinte, mais cela peut rassurer que l’parsing mathématique est appropriée. Pour m’aider dans cette tâche, j’utilise des outils de couverture de code parallèlement à mes expériences, afin de m’assurer que je pratique tous les cas.

Comme exemple très simple, disons que vous vouliez faire un test de cohérence sur la vitesse de sorting des listes du framework .NET. Vous pouvez écrire quelque chose comme ce qui suit, puis parsingr les résultats dans Excel pour vous assurer qu’ils ne dépassent pas une courbe n * log (n).

Dans cet exemple, je mesure le nombre de comparaisons, mais il est également prudent d’examiner le temps réel requirejs pour chaque taille d’échantillon. Cependant, vous devez être encore plus attentif à la mesure de l’algorithme et à l’absence des artefacts de votre infrastructure de test.

 int nCmp = 0; System.Random rnd = new System.Random(); // measure the time required to sort a list of n integers void DoTest(int n) { List lst = new List(n); for( int i=0; ib)?1:0)); } System.Console.Writeline( "{0},{1}", n, nCmp ); } // Perform measurement for a variety of sample sizes. // It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check for( int n = 0; n<1000; n++ ) DoTest(n); 

N’oubliez pas de prendre également en compte les complexités de l’espace qui peuvent également poser problème si vous disposez de ressources mémoire limitées. Ainsi, par exemple, vous pouvez entendre quelqu’un qui souhaite un algorithme à espace constant, ce qui est essentiellement une manière de dire que la quantité d’espace prise par l’algorithme ne dépend d’aucun facteur à l’intérieur du code.

Parfois, la complexité peut provenir du nombre de fois où quelque chose s’appelle, de la fréquence à laquelle une boucle est exécutée, de la fréquence à laquelle la mémoire est allouée, et ainsi de suite.

Enfin, le grand O peut être utilisé dans les cas les plus défavorables, les meilleurs et les cas d’amortissement où, généralement, c’est le pire cas utilisé pour décrire la qualité d’un algorithme.

Ce qui est souvent négligé, c’est le comportement attendu de vos algorithmes. Il ne modifie pas le Big-O de votre algorithme , mais il se rapporte à la déclaration “optimisation prématurée…”

Le comportement attendu de votre algorithme est – très réduit – à quelle vitesse votre algorithme peut fonctionner avec les données que vous êtes le plus susceptible de voir.

Par exemple, si vous recherchez une valeur dans une liste, c’est O (n), mais si vous savez que la plupart des listes que vous voyez ont votre valeur, le comportement typique de votre algorithme est plus rapide.

Pour bien le comprendre, vous devez être capable de décrire la dissortingbution de probabilité de votre “espace de saisie” (si vous devez sortinger une liste, à quelle fréquence cette liste va-t-elle déjà être sortingée? À quelle fréquence est-elle totalement inversée? often is it mostly sorted?) It’s not always feasible that you know that, but sometimes you do.

great question!

If you’re using the Big O, you’re talking about the worse case (more on what that means later). Additionally, there is capital theta for average case and a big omega for best case.

Check out this site for a lovely formal definition of Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.


Ok, so now what do we mean by “best-case” and “worst-case” complexities?

This is probably most clearly illustrated through examples. For example if we are using linear search to find a number in a sorted array then the worst case is when we decide to search for the last element of the array as this would take as many steps as there are items in the array. The best case would be when we search for the first element since we would be done after the first check.

The point of all these adjective -case complexities is that we’re looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm’s complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you’re looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.

Sorry this is so poorly written and lacks much technical information. But hopefully it’ll make time complexity classes easier to think about. Once you become comfortable with these it becomes a simple matter of parsing through your program and looking for things like for-loops that depend on array sizes and reasoning based on your data structures what kind of input would result in sortingvial cases and what input would result in worst-cases.

For code A, the outer loop will execute for n+1 times, the ‘1’ time means the process which checks the whether i still meets the requirement. And inner loop runs n times, n-2 times…. Thus, 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

For code B, though inner loop wouldn’t step in and execute the foo(), the inner loop will be executed for n times depend on outer loop execution time, which is O(n)

I don’t know how to programmatically solve this, but the first thing people do is that we sample the algorithm for certain patterns in the number of operations done, say 4n^2 + 2n + 1 we have 2 rules:

  1. If we have a sum of terms, the term with the largest growth rate is kept, with other terms omitted.
  2. If we have a product of several factors constant factors are omitted.

If we simplify f(x), where f(x) is the formula for number of operations done, (4n^2 + 2n + 1 explained above), we obtain the big-O value [O(n^2) in this case]. But this would have to account for Lagrange interpolation in the program, which may be hard to implement. And what if the real big-O value was O(2^n), and we might have something like O(x^n), so this algorithm probably wouldn’t be programmable. But if someone proves me wrong, give me the code . . . .