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

Translate

La plupart des diplômés en CS sauront certainementBig O signifie. Cela nous aide à mesurer à quel point un algorithme est (in) efficace et si vous savezdans quelle catégorie se situe le problème que vous essayez de résoudrevous pouvez déterminer s'il est encore possible de tirer parti de cette petite performance supplémentaire.1

Mais je suis curieux, comment fairetoicalculer ou estimer la complexité de vos algorithmes?

1 mais comme on dit, 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.

This question and all comments follow the "Attribution Required."

Toutes les réponses

vz0
Translate

Je ferai de mon mieux pour l'expliquer ici en termes simples, mais sachez que ce sujet prend quelques mois à mes étudiants pour enfin le saisir. Vous pouvez trouver plus d'informations sur le chapitre 2 duStructures de données et algorithmes en Javalivre.


Il n'y a pasprocédure mécaniquequi peut être utilisé pour obtenir le BigOh.

En tant que "livre de recettes", pour obtenir leBigOhà partir d'un morceau de code, vous devez d'abord réaliser que vous créez une formule mathématique pour compter le nombre d'étapes de calculs exécutées en fonction d'une entrée d'une certaine taille.

Le but est simple: comparer des algorithmes d'un point de vue théorique, sans avoir besoin d'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 renvoie la somme de tous les éléments du tableau, et nous voulons créer une formule pour compter lescomplexité de calculde cette fonction:

Number_Of_Steps = f(N)

Nous avons doncf(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 comme:

Number_Of_Steps = f(data.length)

Le paramètreNprend ledata.lengthvaleur. Maintenant, nous avons besoin de la définition réelle de la fonctionf(). Cela se fait à partir du code source, dans lequel chaque ligne intéressante est numérotée de 1 à 4.

Il existe de nombreuses 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 prend une constanteCnombre d'étapes de calcul.

Nous allons ajouter 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 de ladatatableau.

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

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

La partie suivante consiste à définir la valeur dufordéclaration. N'oubliez pas que nous comptons le nombre d'étapes de calcul, ce qui signifie que le corps duforl'instruction est exécutéeNfois. C'est la même chose que d'ajouterC, Nfois:

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 duforest exécuté, vous devez le compter en regardant ce que fait le code. Pour simplifier les calculs, nous ignorons les parties d'initialisation de variable, de condition et d'incrémentation dufordéclaration.

Pour obtenir le BigOh réel, nous avons besoin duAnalyse asymptotiquede la fonction. Cela se fait à peu près comme ceci:

  1. Enlevez toutes les constantesC.
  2. Def()obtenir lepolynômedans sonstandard form.
  3. Divisez les termes du polynôme et triez-les par taux de croissance.
  4. Gardez celui qui grandit quandNapprochesinfinity.

Notref()a deux termes:

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

En emportant tous lesCconstantes et parties redondantes:

f(N) = 1 + N ^ 1

Puisque le dernier terme est celui qui grossit quandf()s'approche de l'infini (pensez àlimites) c'est l'argument BigOh, et lesum()function a un BigOh de:

O(N)

Il existe quelques astuces pour résoudre certaines astuces délicates: utilisezsommationsquand tu peux.

À titre d'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 qu'il fallait vous demander est l'ordre d'exécution defoo(). Alors que l'habituel est d'êtreO(1), vous devez demander à vos professeurs à ce sujet.O(1)signifie (presque, principalement) constantC, indépendamment de la tailleN.

leforla déclaration sur la phrase numéro un est délicate. Alors que l'index se termine à2 * N, l'incrément se fait par deux. Cela signifie que le premierforest exécuté uniquementNétapes, et nous devons diviser le nombre par deux.

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

Le numéro de la phrasedeuxest encore plus délicat car cela dépend de la valeur dei. Regardez: l'index i prend les valeurs: 0, 2, 4, 6, 8, ..., 2 * N, et la secondeforêtre exécuté: N fois le premier, N - 2 le second, N - 4 le troisième ... jusqu'au stade N / 2, sur lequel le secondforn'est jamais exécuté.

Sur la formule, cela signifie:

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

Encore une fois, nous comptonsle nombre d'étapes. Et par définition, chaque sommation doit toujours commencer à un et se terminer à un nombre supérieur ou égal à un.

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

(Nous supposons quefoo()estO(1)et prendCpas.)

Nous avons un problème ici: quandiprend la valeurN / 2 + 1vers le haut, la somme intérieure se termine par un nombre négatif! C'est impossible et faux. Nous devons diviser la somme en deux, étant le point pivot du momentiprendN / 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èrei > N / 2, l'intérieurforne sera pas exécuté, et nous supposons une complexité d'exécution C constante sur son corps.

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

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

Appliquer une certaine 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²)
La source
Translate

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 dans le 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, ce serait O (1) car peu importe la taille du tableau, il faut 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 au plus nous aurions à parcourir la liste entière pour trouver notre numéro. Le Big-O est toujours O (n) même si nous pourrions trouver notre numéro le premier essai et parcourir la boucle une fois parce que Big-O décrit la borne supérieure d'un algorithme (oméga est pour la borne inférieure et thêta est pour la borne serrée) .

Quand nous arrivons aux boucles imbriquées:

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

C'est O (n ^ 2) puisque 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 avec n au carré.

Cela efface à peine la surface, mais lorsque vous commencez à analyser des algorithmes plus complexes, des mathématiques complexes impliquant des preuves entrent en jeu. J'espère que cela vous familiarisera au moins avec les bases.

La source
Translate

S'il est utile de savoir comment déterminer le temps 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, issus dehttp://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 recherche de taille constante ou une table de hachage

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

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

Sur2) - Multiplication de deux nombres à n chiffres par un algorithme simple; addition de deux matrices n × n; tri à bulles ou tri par insertion

Sur3) - Multiplication de deux matrices n × n par un algorithme simple

O (cn) - Trouver la solution (exacte) au problème du voyageur de commerce en utilisant la programmation dynamique; déterminer si deux instructions logiques sont équivalentes en utilisant la force brute

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

Surn) - Souvent utilisé à la place de O (n!) Pour dériver des formules plus simples de complexité asymptotique

La source
Translate

Petit rappel: lebig Ola notation est utilisée pour désignerasymptotiquecomplexité (c'est-à-dire lorsque la taille du problème atteint l'infini),etil cache une constante.

Cela signifie qu'entre un algorithme en O (n) et un en O (n2), le 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 le plus rapide).

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

De plus, dans certains cas, le runtime n'est pas une fonction déterministe duTaillen de l'entrée. Prenons par exemple le tri par tri rapide: 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 du tableau.

Il existe différentes complexités temporelles:

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

  • ...

Une bonne introduction estUne introduction à l'analyse des algorithmespar R. Sedgewick et P. Flajolet.

Comme tu dis,premature optimisation is the root of all evil, et (si possible)profilagedevrait toujours être utilisé lors de l'optimisation du code. Cela peut même vous aider à déterminer la complexité de vos algorithmes.

La source
Translate

En voyant les réponses ici, je pense que nous pouvons conclure que la plupart d'entre nous approchent effectivement l'ordre de l'algorithme enregarderet utilisez le bon sens au lieu de le calculer avec, par exemple, leméthode principalecomme on le pensait à l'université. Cela dit, je dois ajouter que même le professeur nous a encouragés (plus tard) à réellementpenseà ce sujet au lieu de simplement le calculer.

Je voudrais également ajouter comment cela se fait pourfonctions 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 récursivement la factorielle du nombre donné.

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

Alors lela performance pour le corps est: O (1)(constant).

Essayez ensuite de déterminer ceci pour lenombre d'appels récursifs. Dans ce cas, nous avons n-1 appels récursifs.

Alors leles performances pour les appels récursifs sont: O (n-1)(l'ordre est n, car nous jetons les parties insignifiantes).

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

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


Peter, répondrevos problèmes soulevés;la méthode que je décris ici gère assez bien cela. Mais gardez à l'esprit que c'est toujours unapproximationet non 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 la factorielle que j'ai utilisée dans cet exemple.
Bien sûr, tout dépend de la façon dont vous pouvez estimer le temps d'exécution du corps de la fonction et du nombre d'appels récursifs, mais c'est tout aussi vrai pour les autres méthodes.

La source
Translate

Si votre coût est un polynôme, gardez simplement le terme d'ordre le plus élevé, sans son multiplicateur. Par exemple:

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, 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 (logN) <O (N) <O (NJournalN) <O (N2) <O (Nk) <O (en) <O (n!)

La source
Translate

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

Votre outil de base est le concept des points de décision et leur entropie. L'entropie d'un point de décision est l'information moyenne qu'il vous donnera. Par exemple, si un programme contient un point de décision avec deux branches, son entropie est la somme de la probabilité de chaque branche multipliée par le log2de la probabilité inverse de cette branche. C'est tout ce que vous apprenez en exécutant cette décision.

Par exemple, unifinstruction ayant deux branches, 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. Donc son entropie est de 1 bit.

Supposons que vous recherchiez 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 le rechercher avec des instructions IF qui ont des résultats tout aussi probables, il devrait prendre 10 décisions.

C'est ce que vous obtenez avec la recherche binaire.

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 que ce soit le cas et 1023/1024 que ce ne soit pas le cas. L'entropie de cette décision est de 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, c'est exponentiel en nombre de bits que vous devez apprendre.

Supposons que vous effectuez une indexation. Supposons que la table soit pré-triée dans un grand nombre de casiers et que vous utilisiez une partie de tous les bits de la clé pour indexer directement l'entrée de la table. S'il y a 1024 bins, l'entropie est 1/1024 * log (1024) + 1/1024 * log (1024) + ... pour 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 l'indexation de la recherche est rapide.

Pensez maintenant au tri. 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'ajouter à la liste. Le tri prend donc environ N fois le nombre d'étapes de la recherche sous-jacente.

Ainsi, les tris basés sur des décisions binaires ayant des résultats à peu près également probables prennent tous environ O (N log N) étapes. Un algorithme de tri O (N) est possible s'il est basé sur une recherche d'indexation.

J'ai constaté que presque tous les problèmes de performances algorithmiques peuvent être examinés de cette manière.

La source
Translate

Commençons par le début.

Tout d'abord, acceptez le principe selon lequel certaines opérations simples sur les données peuvent être effectuéesO(1)temps, c'est-à-dire dans le temps qui est indépendant 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. Opérations d'accès à la structure (par exemple, indexation de tableau comme A [i], ou pointeur suivant avec l'opérateur ->).
  5. Affectation simple telle que la copie d'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 machine; souvent, une ou deux instructions seulement sont nécessaires. Par conséquent, plusieurs types d'instructions en C peuvent être exécutés dansO(1)temps, c'est-à-dire dans une durée constante indépendante de l'entrée. Ces simples comprennent

  1. Instructions d'affectation qui n'impliquent pas d'appels de fonction dans leurs expressions.
  2. Lisez les déclarations.
  3. Écrivez des instructions qui ne nécessitent pas d'appels de fonction pour évaluer les arguments.
  4. Les instructions jump break, continue, goto et return expression, où 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 dans la boucle. La boucle for se termine lorsque l'index atteint une certaine limite. Par exemple, la boucle for

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 i atteint n - 1.

Cependant, pour le moment, concentrez-vous sur la forme simple de la boucle for, où lela différence entre les valeurs finale et initiale, divisée par le montant de l'incrémentation de la variable d'index, nous indique combien de fois nous faisons le tour de la boucle. Ce nombre est exact, sauf s'il existe des moyens de quitter la boucle via une instruction jump; c'est une limite supérieure du 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 (c'est-à-dire que lorsque i atteint 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 borne supérieure big-oh pour le corps par le nombre de fois autour de la boucle. Strictement parlant, il faut alorsajouter le temps O (1) pour initialiser l'index de boucle et le temps O (1) pour la première comparaison de l'index de boucle avec la limite, parce que nous testons une fois de plus que nous faisons le tour de la boucle. Cependant, à moins qu'il ne soit possible d'exécuter la boucle zéro fois, le temps d'initialisation de la boucle et de tester la limite une fois est un terme de poids 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 savons queligne 1)prendO(1)temps. Clairement, on fait le tour de la boucle n fois, comme on peut le déterminer en soustrayant la limite inférieure de la limite supérieure trouvée sur la ligne (1) puis en ajoutant 1. Puisque le corps, ligne (2), prend O (1) temps, on peut négliger le temps d'incrémentation j et le temps de comparaison de j avec n, tous deux étant également O (1). Ainsi, le temps de parcours des lignes (1) et (2) est leproduit de n et O (1), lequel estO(n).

De même, nous pouvons limiter le temps d'exécution de la boucle externe constitué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 du temps O (n). Ainsi, nous pouvons négliger le temps O (1) pour incrémenter i et tester si i <n à chaque itération, concluant que chaque itération de la boucle externe prend O (n) temps.

L'initialisation i = 0 de la boucle externe et le (n + 1) er test de la condition i <n prennent également un temps O (1) et peuvent être négligés. Enfin, nous observons que nous faisons le tour de la boucle externe n fois, en prenant un temps O (n) pour chaque itération, donnant un totalO(n^2)temps de fonctionnement.


Un exemple plus pratique.

enter image description here

La source
Translate

Si vous souhaitez estimer l'ordre de votre code de manière empirique plutôt qu'en analysant le code, vous pouvez vous en tenir à une série de valeurs croissantes de n et de chronométrer votre code. Tracez vos horaires sur une échelle logarithmique. 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 s'approche de son ordre asymptotique. De plus, vous pouvez constater que certains codes que vous pensiez être de l'ordre O (x) sont en réalité de l'ordre O (x ^ 2), par exemple, à cause du temps passé dans les appels de bibliothèque.

La source
Translate

Fondamentalement, ce qui revient 90% du temps, c'est simplement l'analyse des boucles. Avez-vous des boucles imbriquées simples, doubles, triples? Le vous avez O (n), O (n ^ 2), O (n ^ 3) temps d'exécution.

Très rarement (à moins que vous n'écriviez une plate-forme avec une bibliothèque de base étendue (comme par exemple, le .NET BCL ou le STL de C ++), vous rencontrerez quelque chose de plus difficile que de simplement regarder vos boucles (pour les déclarations, alors que, allez, etc...)

La source
Gustave Lee
Translate

La notation Big O est utile car elle est facile à utiliser et cache les complications et les détails inutiles (pour une définition de inutile). La méthode arborescente est une manière intéressante de résoudre la complexité des algorithmes de division et de conquête. Disons que vous avez une version de tri rapide avec la procédure médiane, de sorte que vous divisez le tableau en sous-tableaux parfaitement équilibrés à chaque fois.

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

Puisque nous pouvons trouver la médiane en temps O (n) et diviser le tableau en deux parties en temps O (n), le travail effectué à chaque nœud est O (k) où k est la taille du tableau. Chaque niveau de l'arbre contient (au plus) le tableau entier donc le travail par niveau est O (n) (les tailles des sous-tableaux s'additionnent à n, et puisque nous avons O (k) par niveau, nous pouvons additionner cela) . Il n'y a que des niveaux log (n) dans l'arborescence puisque chaque fois que nous divisons par deux l'entrée.

Par conséquent, nous pouvons limiter la quantité de travail par O (n * log (n)).

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

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

et supposons simplement que a et b sont des BigIntegers en Java ou quelque chose qui peut gérer des nombres arbitrairement grands. La plupart des gens diraient qu'il s'agit d'un algorithme O (n) sans broncher. Le raisonnement est que vous avez n itérations dans la boucle for et que O (1) travaille à côté de la boucle.

Mais les nombres de Fibonacci sont grands, le n-ième nombre de Fibonacci est exponentiel en n donc juste le stocker prendra de l'ordre de n octets. Effectuer une addition avec de grands nombres entiers demandera 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 quadradique!

La source
Translate

Moins utile en général, je pense, mais par souci d'exhaustivité, il y a aussi unBig Omega Ω, qui définit une borne inférieure sur la complexité d'un algorithme, et unBig Thêta Θ, qui définit à la fois une limite supérieure et inférieure.

La source
Translate

Décomposez l'algorithme en morceaux pour lesquels vous connaissez la notation en gros O et combinez-les via de gros opérateurs O. C'est le seul moyen que je connaisse.

Pour plus d'informations, consultez lePage Wikipédiasur le sujet.

La source
Translate

Connaissance des algorithmes / structures de données que j'utilise et / ou analyse rapide de l'imbrication d'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 ils utilisent. Peut-être que les fonctions de bibliothèque devraient avoir une mesure de complexité / efficacité, que ce soit Big O ou une autre métrique, disponible dans la documentation ou mêmeIntelliSense.

La source
Translate

Quant à "comment calculez-vous" Big O, cela fait partie deThéorie de la complexité informatique. Pour certains (nombreux) cas particuliers, vous pourrez peut-être proposer des heuristiques simples (comme multiplier le nombre de boucles pour les boucles imbriquées), esp. quand tout ce que vous voulez, c'est une estimation de la limite supérieure, et que cela ne vous dérange pas si elle est trop pessimiste - ce qui, je suppose, est probablement le sujet de votre question.

Si vous voulez vraiment répondre à votre question pour un algorithme, le mieux que vous puissiez faire est d'appliquer la théorie. En plus de l'analyse simpliste du «pire des cas», j'ai trouvéAnalyse amortietrès utile dans la pratique.

La source
Translate

Pour le 1er cas, la boucle interne est exécutéen-ifois, donc le nombre total d'exécutions est la somme deivenir de0àn-1(parce que inférieur, non inférieur ou égal) dun-i. Vous obtenez enfinn*(n + 1) / 2, alorsO(n²/2) = O(n²).

Pour la 2ème boucle,iest entre0etninclus pour la boucle extérieure; alors la boucle interne est exécutée quandjest strictement supérieur àn, ce qui est alors impossible.

La source
Translate

En plus d'utiliser la méthode maître (ou l'une de ses spécialisations), je teste mes algorithmes expérimentalement. Ça ne peut pasprouverqu'une classe de complexité particulière est atteinte, mais cela peut donner l'assurance que l'analyse mathématique est appropriée. Pour aider avec cette assurance, j'utilise des outils de couverture de code en conjonction avec mes expériences, pour m'assurer que j'exerce tous les cas.

À titre d'exemple très simple, disons que vous vouliez faire une vérification de cohérence sur la vitesse du tri de liste du framework .NET. Vous pouvez écrire quelque chose comme ce qui suit, puis analyser 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 requis pour chaque taille d'échantillon. Cependant, vous devez être encore plus prudent en ne mesurant que l'algorithme et en n'incluant pas les 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<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?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);
La source
Translate

N'oubliez pas de tenir compte également des complexités de l'espace qui peuvent également être une source de préoccupation si vous avez des ressources mémoire limitées. Ainsi, par exemple, vous pouvez entendre quelqu'un vouloir un algorithme d'espace constant, ce qui est essentiellement une façon de dire que la quantité d'espace occupée 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 est appelé, de la fréquence à laquelle une boucle est exécutée, de la fréquence d'allocation de la mémoire, et ainsi de suite est une autre partie pour répondre à cette question.

Enfin, big O peut être utilisé pour le pire des cas, le meilleur des cas et les cas d'amortissement où c'est généralement le pire des cas qui est utilisé pour décrire à quel point un algorithme peut être mauvais.

La source
Translate

Ce qui est souvent négligé, c'est leattenducomportement de vos algorithmes.Cela ne change 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 stupide - à quelle vitesse vous pouvez vous attendre à ce que votre algorithme fonctionne sur 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 à l'avance, le comportement typique de votre algorithme est plus rapide.

Pour vraiment le clouer, vous devez être capable de décrire la distribution de probabilité de votre "espace d'entrée" (si vous avez besoin de trier une liste, à quelle fréquence cette liste va-t-elle déjà être triée? À quelle fréquence est-elle totalement inversée? est-ce souvent trié?) Ce n'est pas toujours possible que vous le sachiez, mais parfois vous le savez.

La source
Translate

super question!

Avertissement: cette réponse contient de fausses déclarations, voir les commentaires ci-dessous.

Si vous utilisez le Big O, vous parlez du pire des cas (plus d'informations sur ce que cela signifie plus tard). De plus, il existe un thêta majuscule pour le cas moyen et un gros oméga pour le meilleur cas.

Consultez ce site pour une belle définition formelle de Big O:https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f (n) = O (g (n)) signifie qu'il existe des constantes positives c et k, telles que 0 ≤ f (n) ≤ cg (n) pour tout n ≥ k. Les valeurs de c et k doivent être fixes pour la fonction f et ne doivent pas dépendre de n.


Ok, alors maintenant qu'entendons-nous par les complexités du «meilleur des cas» et du «pire des cas»?

Ceci est probablement le plus clairement illustré par des exemples. Par exemple, si nous utilisons la recherche linéaire pour trouver un nombre dans un tableau trié, lepire casc'est quand nous décidons derechercher le dernier élémentdu tableau car cela prendrait autant d'étapes qu'il y a d'éléments dans le tableau. lemeilleur casserait quand nous cherchons lepremier élémentpuisque nous aurions fini après le premier contrôle.

Le point de tout celaadjectifLa complexité des cas est que nous cherchons un moyen de représenter graphiquement la durée d'exécution d'un programme hypothétique jusqu'à son terme en termes de taille de variables particulières. Cependant, pour de nombreux algorithmes, vous pouvez affirmer qu'il n'y a pas une seule heure pour une taille d'entrée particulière. Notez que cela est en contradiction avec l'exigence fondamentale d'une fonction, toute entrée ne doit pas avoir plus d'une sortie. Alors on arrive avecplusieursfonctions pour décrire la complexité d'un algorithme. Maintenant, même si la recherche d'un tableau de taille n peut prendre un temps variable selon ce que vous recherchez dans le tableau et proportionnellement à n, nous pouvons créer une description informative de l'algorithme en utilisant le meilleur cas et les classes les plus défavorables.

Désolé, c'est si mal écrit et il manque beaucoup d'informations techniques. Mais j'espère que cela facilitera la réflexion sur les classes de complexité temporelle. Une fois que vous vous êtes familiarisé avec ceux-ci, il devient simple d'analyser votre programme et de rechercher des éléments tels que des boucles for qui dépendent de la taille des tableaux et du raisonnement basé sur vos structures de données, quel type d'entrée entraînerait des cas triviaux et quelle entrée en résulterait. dans le pire des cas.

La source
Translate

Je ne sais pas comment résoudre cela par programme, mais la première chose que les gens font est que nous échantillonnons l'algorithme pour certains modèles dans le nombre d'opérations effectuées, disons 4n ^ 2 + 2n + 1, nous avons 2 règles:

  1. Si nous avons une somme de termes, le terme ayant le taux de croissance le plus élevé est conservé, les autres termes étant omis.
  2. Si nous avons un produit de plusieurs facteurs, les facteurs constants sont omis.

Si nous simplifions f (x), où f (x) est la formule du nombre d'opérations effectuées, (4n ^ 2 + 2n + 1 expliqué ci-dessus), nous obtenons la valeur big-O [O (n ^ 2) dans ce Cas]. Mais cela devrait tenir compte de l'interpolation de Lagrange dans le programme, qui peut être difficile à mettre en œuvre. Et si la vraie valeur big-O était O (2 ^ n), et que nous pourrions avoir quelque chose comme O (x ^ n), donc cet algorithme ne serait probablement pas programmable. Mais si quelqu'un me prouve que j'ai tort, donnez-moi le code. . . .

La source
Translate

Pour le code A, la boucle externe s'exécutera pendantn+1fois, le temps «1» signifie le processus qui vérifie si je répond toujours à l'exigence. Et la boucle intérieure fonctionnenfois,n-2fois ... Ainsi,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

Pour le code B, bien que la boucle interne n'intervienne pas et n'exécute pas foo (), la boucle interne sera exécutée n fois en fonction du temps d'exécution de la boucle externe, qui est O (n)

La source
HmT
Translate

Je voudrais expliquer le Big-O sous un aspect un peu différent.

Big-O consiste simplement à comparer la complexité des programmes, c'est-à-dire à quelle vitesse croissent-ils lorsque les intrants augmentent et non le temps exact consacré à l'action.

À mon humble avis, dans les formules big-O, il vaut mieux ne pas utiliser d'équations plus complexes (vous pouvez vous en tenir à celles du graphique suivant.) Cependant, vous pouvez toujours utiliser une autre formule plus précise (comme 3 ^ n, n ^ 3, .. .) mais plus que cela peut parfois être trompeur! Il vaut donc mieux garder les choses aussi simples que possible.

enter image description here

Je tiens à souligner une fois de plus qu'ici nous ne voulons pas obtenir une formule exacte pour notre algorithme. Nous voulons seulement montrer comment il se développe lorsque les entrées augmentent et comparer avec les autres algorithmes dans ce sens. Sinon, vous feriez mieux d'utiliser différentes méthodes comme le benchmarking.

La source