Big O, comment calculez-vous/en approchant?

https://stackoverflow.com/questions/3255

08-06-2019
|

Question

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 à l' dans quelle catégorie le problème que vous essayez de résoudre réside dans vous pouvez voir si il est encore possible de faire sortir le petit plus de performance.¹

Mais je suis curieux, comment faire vous calcul approximatif de la complexité des algorithmes?

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

La solution

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 la Structures de données et Algorithmes en Java livre.

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

Comme un "livre de cuisine", afin d'obtenir le 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 la complexité algorithmique 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 tels que:

Number_Of_Steps = f(data.length)

Le paramètre N prend le 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 la 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 la for l'énoncé.Rappelez-vous que l'on compte le nombre d'étapes de calcul, ce qui signifie que le corps de la for instruction est exécutée N fois.C'est le même que l'ajout de 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 for 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 pièces de la for l'énoncé.

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

Emporter tous les constantes C.
À partir de f() obtenez de l' polynomium dans son standard form.
Diviser les termes de la polynomium et de les trier par le taux de croissance.
Garder celui qui prend de l'ampleur lorsque N approches infinity.

Notre f() a deux conditions:

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

Emportant tous les C les constantes et les parties redondantes:

f(N) = 1 + N ^ 1

Depuis le dernier terme est celui qui grandit quand f() approche de l'infini (pensez à limites)) c'est la BigOh argument, et la sum() la fonction de la BigOh de:

O(N)

Il y a quelques astuces pour résoudre des problèmes de ceux:utilisation sommations chaque fois que vous le pouvez.

Comme un 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 que vous besoin d'être posée est de l'ordre de l'exécution de foo().Alors que l'habitude est d'être O(1), vous devez demander à vos professeurs à ce sujet. O(1) les moyens (ou presque, la plupart du temps) constante C, indépendant de la taille N.

L' for déclaration sur le nombre de phrase est délicat.Alors que l'indice se termine à 2 * N, l'incrément est fait par deux.Cela signifie que la première for est exécuté uniquement N les é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)( ... )

Le nombre de phrase 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 deuxième for exécuté:N fois la première, N - 2, le deuxième, N - 4, le troisième...jusqu'à la N / 2 scène, sur laquelle la deuxième 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 que foo() est O(1) et prend C les étapes.)

Nous avons un problème ici:lorsque 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 prend 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 central i > N / 2, à l'intérieur for ne sera pas exécuté, 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é:

Sommation(w de 1 à N)( C ) = N * C
Sommation(w de 1 à N)( A (+/-) B ) = Somme(w de 1 à N)( A ) (+/-) Somme(w de 1 à N)( B )
Sommation(w de 1 à N)( w * C ) = C * Sommation(w de 1 à N)( w ) (C est une constante, indépendante de w)
Sommation(w de 1 à N)( w ) = (N * (N + 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²)

Autres conseils

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++){
    if(array[i] == numToFind){ return 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:

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

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 principes de base à la moins bien.

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'aide 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²) - 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³) - Multiplication de deux n×n matrices par un algorithme simple

O(cⁿ) - 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ⁿ) - Souvent utilisé au lieu de O(n!) pour dériver des formules plus simples pour asymptotique de la complexité

Petit rappel:l' big O la notation est utilisé pour désigner asymptotique 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²), 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 l' taille n de l'entrée.Prendre le tri à l'aide de la fonction de tri rapide 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 du tableau.

Il y a différents temps complexités:

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 est Une Introduction à l'Analyse des Algorithmes par R.Sedgewick et P.Flajolet.

Comme vous le dites, premature optimisation is the root of all evil, et (si possible) profilage vraiment devrait toujours être utilisé lors de l'optimisation de code.Il peut même vous aider à déterminer la complexité des algorithmes.

Voir les réponses ici, je pense que nous pouvons conclure que la plupart d'entre nous ne sont en effet approximative de l'ordre de l'algorithme par la recherche et utiliser le bon sens au lieu de calculer, par exemple, l' maître de la méthode comme nous avons pensé à l'université.Avec cela dit, je dois ajouter que même le professeur nous a encouragés (plus tard) à la réalité pense à ce sujet, au lieu de simplement calculer.

Aussi, je tiens à ajouter comment cela est fait pour fonctions récursives:

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

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

qui de manière récursive qui calcule la factorielle d'un nombre donné.

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

De sorte que le performance pour le corps:O(1) (constant).

Prochaine tentative et de déterminer ce pour la nombre d'appels récursifs.Dans ce cas, nous avons n-1 appels récursifs.

De sorte que le les performances pour les appels récursifs est:O(n-1) (ordre n, que l'on jette de l'insignifiant pièces).

Puis mettre les deux ensemble et vous avez alors la performance pour l'ensemble de la fonction récursive:

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

Peter, pour répondre à votre a soulevé des questions; la méthode que je décris ici gère en fait cela très bien.Mais gardez à l'esprit que c'est encore un rapprochement et pas un plein mathématiquement bonne réponse.La méthode décrite ici est également l'une des méthodes qui nous a été enseigné à l'université, et si je me souviens bien, a été utilisé pour beaucoup plus avancé des algorithmes de la factorielle j'ai utilisé 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 le nombre d'appels récursifs, mais qui est tout aussi vrai pour les autres méthodes.

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(n²/4 + n/2) = O(n²/4) = O(n²)

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 journal N) < O(N²) < O(N^k) < O(eⁿ) < O(n!)

J'y pense en termes d'information.Tout le 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 point de décision est la moyenne de l'information qu'il vous donnera.Par exemple, si un programme contient un point de décision à deux branches, c'est l'entropie est la somme de la probabilité de chaque branche de fois le journal₂ de l'inverse de la probabilité de cette branche.C'est combien vous apprendre par l'exécution de cette décision.

Par exemple, un if déclaration ayant deux branches, à la fois tout aussi probable, a une entropie de 1/2 * log(2/1) + 1/2 * journal(2/1) = 1/2 * 1 + 1/2 * 1 = 1.Donc son entropie est de 1 bit.

Supposons que vous êtes à la recherche d'un tableau de N éléments, comme N=1024.C'est un 10 bits problème car log(1024) = 10 bits.Donc, si vous pouvez rechercher SI les états qui ont des résultats équiprobables, il devrait prendre 10 décisions.

C'est ce que vous obtenez avec les binaires de recherche.

Supposons que vous faites la recherche linéaire.Vous regardez le premier élément et lui demander si c'est celui que vous voulez.Les probabilités sont 1/1024 qu'il est, et 1023/1024 qu'il ne l'est pas.L'entropie de cette décision est 1/1024*log(1024/1) + 1023/1024 * journal(1024/1023) = 1/1024 * 10 + 1023/1024 * sur 0 = sur .01 peu.Vous avez appris très peu de choses!La seconde décision n'est pas beaucoup mieux.C'est pourquoi la recherche linéaire est si lent.En fait, c'est exponentiel dans le nombre de bits que vous devez apprendre.

Supposons que vous faites de l'indexation.Supposons que le tableau est trié dans un tas de poubelles, et de l'utilisation de certains de tous les bits de la clé d'index directement à l'entrée de la table.Si il y a 1024 bacs, l'entropie est 1/1024 * log(1024) + 1/1024 * log(1024) + ...pour tous 1024 résultats possibles.C'est 1/1024 * 10 fois 1024 résultats, ou 10 bits d'entropie pour qu'une opération d'indexation.C'est pourquoi l'indexation de la recherche est rapide.

Maintenant, pensez à trier.Vous disposez de N éléments, et vous avez une liste.Pour chaque élément, vous avez à la recherche de l'emplacement de l'élément va dans la liste, puis l'ajouter à la liste.Tri prend à peu près N fois le nombre d'étapes de la recherche sous-jacente.

Donc, sortes basée sur des décisions binaires ayant à peu près aussi susceptibles les résultats de tous les prendre sur O(N log N) étapes.Un O(N) algorithme de tri est possible que si elle est basée sur l'indexation de la recherche.

J'ai trouvé que presque tous algorithmique des problèmes de performances peut être vu de cette façon.

Permet de commencer depuis le début.

Tout d'abord, accepter le principe que certaines opérations simples sur des données peut être fait dans O(1) le temps, qui est, dans le temps qui est indépendant de la taille de l'entrée.Ces opérations primitives dans C se composent de

Opérations arithmétiques (par ex.+ ou %).
Des opérations logiques (par exemple, &&).
Les opérations de comparaison (p. ex., <=).
Structure d'accès de l'exploitation (p. ex.tableau d'indexation comme Un[i], ou un pointeur fol- la diminution avec l' -> opérateur).
Affectation Simple, telle que la copie d'une valeur dans une variable.
Les appels aux fonctions de la bibliothèque (par exemple, scanf, printf).

La justification de ce principe nécessite une étude détaillée de la machine des instructions (étapes primitives) d'un ordinateur standard.Chaque décrit les opérations peuvent être effectuées avec un nombre limité d'instructions machine;souvent seulement un ou deux instructions sont nécessaires.En conséquence, plusieurs sortes de déclarations en C peut être exécutée dans O(1) le temps, qui est, dans certains temps constant indépendant de l'entrée.Ces simples comprennent

Les instructions d'affectation qui n'impliquent pas les appels de fonction dans leurs expressions.
Lire une déclaration.
Instructions d'écriture qui ne nécessitent pas d'appels de la fonction à évaluer des arguments.
Le saut états pause, continuer, goto, et le retour de l'expression, où l'expression ne contient pas un appel de fonction.

En C, de nombreux pour les boucles sont formées par l'initialisation d'une variable d'index à une certaine valeur et l'incrémentation de la variable de 1 à chaque fois autour de la boucle.Le pour-boucle se termine lorsque l'indice 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 j'.Il incrémente i de 1 à chaque fois autour de la boucle, et les itérations arrêter quand j'ai atteint n − 1.

Cependant, pour le moment, se concentrer sur la forme simple de la boucle for, où l' la différence entre la finale et initiale des valeurs, divisée par le montant par lequel l'indice de la variable est incrémentée nous dit combien de fois nous faisons le tour de la boucle.Ce comte est exacte, à moins qu'il existe des moyens de sortir de la boucle par une instruction de saut;c'est une limite supérieure sur le nombre d'itérations dans tous les cas.

Par exemple, la boucle for parcourt ((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, quand je atteint n−1, la boucle s'arrête et aucune itération se produit avec i = n−1), et 1 est ajouté de i à chaque itération de la boucle.

Dans le cas le plus simple, où le temps passé dans le corps de la boucle est la même pour chaque itération, nous pouvons multiplier le grand-oh limite supérieure du corps par le nombre de fois le tour de la boucle.Strictement parlant, nous devons alors ajouter O(1) fois pour initialiser l'indice de boucle et O(1) pour la première comparaison de l'indice de boucle avec le limite, parce que nous avons test une fois de plus que nous faisons le tour de la boucle.Cependant, à moins que il est possible d'exécuter la boucle zéro fois, le temps d'initialiser la boucle et test la limite d'une fois est d'ordre faible, qui peut être diminué par la règle de sommation.

Maintenant, considérons cet exemple:

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

Nous savons que ligne (1) prend O(1) temps.Clairement, nous faisons le tour de la boucle n fois, comme nous pouvons déterminer par la soustraction de la limite inférieure de la limite supérieure de la trouver sur la ligne (1), puis en ajoutant 1.Depuis le corps, la ligne (2), prend O(1) fois, on ne peut négliger les temps pour incrémenter j, et le temps de comparer les j avec n, qui sont tous deux également en O(1).Ainsi, le temps d'exécution de lignes (1) et (2) est le produit de n et O(1), qui est O(n).

De même, nous avons lié le temps d'exécution de la boucle externe composé de 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 de lignes (3) et (4) est O(n) fois.Ainsi, nous pouvons négliger le O(1) fois pour incrémenter i et de tester si je < n dans à chaque itération, la conclusion que chaque itération de la boucle externe prend O(n) fois.

L'initialisation i = 0 de la boucle externe et la (n + 1)st test de la condition j' < n de même prendre en O(1) en temps et peuvent être négligées.Enfin, nous observons que nous allons autour de la boucle externe n fois, de prendre O(n) pour chaque itération, ce qui donne un total O(n^2) temps d'exécution.

Un exemple.

enter image description here

Si vous souhaitez estimer l'ordre de votre code de façon empirique plutôt que par l'analyse du code, vous pourriez rester dans une série de valeurs croissantes de n et le temps de votre code.Tracer votre timings sur une échelle logarithmique.Si le code est O(x^n), les valeurs doivent tomber sur une ligne de pente n.

Cela a plusieurs avantages plus de simplement étudier le code.Pour une chose, vous pouvez voir si vous êtes dans la gamme où le temps d'exécution à l'approche asymptotique de la commande.Aussi, vous pouvez constater que certains de code que vous avez pensé était de l'ordre de O(x), c'est vraiment de l'ordre de O(x^2), par exemple, parce que de temps passé dans la bibliothèque des appels.

Fondamentalement, la chose que les cultures jusqu'à 90% du temps, c'est juste l'analyse des boucles.Avez-vous des simples, doubles, triples boucles imbriquées?Vous avez O(n), O(n^2), O(n^3) temps de fonctionnement.

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

Briser l'algorithme en morceaux que vous connaissez le grand O de notation, et de les combiner par big O opérateurs.C'est la seule façon que je connaisse.

Pour plus d'informations, consultez la Page Wikipedia sur le sujet.

Big O la notation est utile, car il est facile à travailler et se cache des complications inutiles et les détails (pour une définition de l'inutile).Une belle façon de travailler la complexité de diviser et conquérir les algorithmes de la méthode d'arbre.Disons que vous avez une version de quicksort à la médiane de la procédure, de sorte que vous diviser le tableau en parfait équilibre de sous-tableaux à chaque fois.

Maintenant construire un arbre correspondant à tous les groupes avec qui 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 avez un seul élément des tableaux en bas.

Depuis, nous pouvons trouver la médiane en O(n) le temps et de diviser le tableau en deux parties en O(n) le temps, le travail effectué à chaque nœud est O(k), où k est la taille du tableau.Chaque niveau de l'arbre contient (au plus) à l'ensemble de la matrice de sorte que le travail par niveau est O(n) (la taille des sous-réseaux ajouter jusqu'à n, et comme nous avons de O(k) par niveau, nous pouvons ajouter à cette place).Il y a seulement log(n) niveaux dans l'arbre depuis à chaque fois que nous réduire de moitié l'entrée.

Donc, on peut à la limite supérieure de la quantité de travail par O(n*log(n)).

Toutefois, Big O cache quelques détails qui parfois nous ne pouvons pas ignorer.Envisager le calcul de la suite de Fibonacci avec

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

et permet de supposer a et b sont BigIntegers en Java ou quelque chose qui peut manipuler arbitrairement grand nombre.La plupart des gens disent que c'est un algorithme O(n) sans broncher.Le raisonnement est que vous avez n itérations de la boucle et O(1) travail à côté de la boucle.

Mais les nombres de Fibonacci sont grandes, le n-ème nombre de Fibonacci est exponentielle en n, donc juste le stockage, il prendra de l'ordre de n octets.L'exécution d'addition avec de grands entiers prendra O(n) la quantité de travail.De sorte que le montant total des travaux effectués au cours de cette procédure est

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

Donc, cet algorithme s'exécute en quadradic temps!

La familiarité avec les algorithmes/structures de données que j'utilise et/ou rapide coup d'œil à l'analyse de l'itération de nidification.La difficulté, c'est quand vous appelez une fonction de la bibliothèque, éventuellement plusieurs fois, vous pouvez souvent être sûr de ce que vous appelez la fonction inutilement à des moments ou la mise en œuvre qu'ils utilisent.Peut-être les fonctions de la bibliothèque doit avoir une complexité et la mesure d'efficacité, que ce soit le Big O ou une autre métrique, qui est disponible dans les documents ou même IntelliSense.

Moins utile en général, je pense, mais par souci d'exhaustivité, il est également un Gros Omega Ω, qui définit une limite inférieure sur un algorithme de complexité, et d'une Big Thêta Θ, qui définit à la fois une limite supérieure et de limite inférieure.

Comme "comment voulez-vous calculer le" Big O, c'est une partie de La complexité algorithmique de la théorie.Pour certains (nombreux) cas spéciaux, vous pourriez être en mesure de venir avec certains de simples heuristiques (comme en multipliant boucle compte de boucles imbriquées), esp.quand tout ce que vous voulez, c'est toute la limite supérieure de l'estimation, et vous n'avez pas l'esprit si elle est trop pessimiste, qui je pense est probablement ce que votre question est à propos.

Si vous voulez vraiment répondre à votre question pour n'importe quel algorithme, le meilleur que vous pouvez faire est d'appliquer la théorie.En plus de simpliste "pire des cas" l'analyse que j'ai trouvé Amorti analyse très utile dans la pratique.

Pour le 1er cas, la boucle interne est exécutée n-i fois, de sorte que le nombre total d'exécutions est la somme pour i allant de 0 pour n-1 (à cause de la baisse de, pas inférieur ou égal) de la n-i.Vous obtenez finalement n*(n + 1) / 2, de sorte O(n²/2) = O(n²).

Pour la 2ème boucle, i est entre 0 et n inclus pour la boucle externe;ensuite, la boucle interne est exécutée lors de l' j est strictement supérieur à n, qui est impossible.

En plus de l'aide de la méthode maître (ou de l'une de ses spécialisations), je test mon algorithmes expérimentalement.Cela ne peut pas prouver une classe de complexité est atteint, mais il peut donner l'assurance que l'analyse mathématique est approprié.Pour aider avec cette assurance, j'utilise les outils de couverture de code en conjonction avec mes expériences, pour s'assurer que je fais du sport tous les cas.

Comme un exemple simple, supposons que vous vouliez faire un test de cohérence sur la vitesse de la .NET framework de tri de la liste.Vous pouvez écrire quelque chose comme ce qui suit, puis analyser les résultats dans Excel afin de s'assurer qu'ils ne dépassent pas un n*log(n) de la courbe.

Dans cet exemple, je mesure le nombre de comparaisons, mais il est également prudent d'examiner le temps de travail nécessaire pour chaque taille de l'échantillon.Cependant, alors vous devez être encore plus prudent que vous êtes simplement en mesure de l'algorithme et de ne pas y compris 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);

N'oubliez pas également de faire de la place complexités qui peuvent également être une cause d'inquiétude si l'on a limité les ressources de la mémoire.Ainsi, par exemple, vous pouvez entendre quelqu'un qui veut une constante de l'espace de l'algorithme qui est essentiellement une manière de dire que la quantité d'espace utilisé par l'algorithme ne dépend pas des facteurs à l'intérieur du code.

Parfois, la complexité peut venir de la façon dont beaucoup de temps est quelque chose qui s'appelle, combien de fois est une boucle exécutée, quelle est la fréquence de la mémoire allouée, et ainsi de suite est une autre partie de répondre à cette question.

Enfin, big O peut être utilisé pour le pire des cas, dans le meilleur des cas, et de l'amortissement des cas où il est généralement le pire des cas, qui est utilisé pour décrire comment les mauvais algorithme peut être.

Ce qui est souvent négligée, est l' attendu le comportement des algorithmes. Il ne change pas le Big-O de votre algorithme, mais il ne se rapportent à la déclaration de "l'optimisation prématurée...."

Le comportement attendu de votre algorithme est -- très abrutir -- à quelle vitesse vous pouvez attendre de votre algorithme de travailler sur des données qui vous êtes le plus susceptible de voir.

Par exemple, si vous êtes à la recherche d'une valeur dans une liste, il est O(n), mais si vous savez que la plupart des listes vous voyez votre valeur à l'avant, un comportement typique de votre algorithme est plus rapide.

Vraiment des ongles vers le bas, vous devez être en mesure de décrire la distribution de probabilité de votre "espace d'entrée" (si vous avez besoin de trier une liste, quelle est la fréquence de cette liste sera déjà triés?combien de fois est-il totalement inversée?quelle est la fréquence de la plupart triés?) Il n'est pas toujours faisable que vous savez cela, mais parfois vous faites.

excellente question!

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

Si vous êtes à l'aide de la Big O, vous parlez le pire des cas (plus de détails sur ce que cela signifie que plus tard).En outre, il est capital de thêta pour la moyenne des cas et un gros omega pour le meilleur des 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, tel que 0 ≤ f(n) ≤ cg(n) pour tout n ≥ k.Les valeurs de c et k doit être fixé pour la fonction f et ne doit pas dépendre de n.

Ok, alors maintenant, qu'entendons-nous par "meilleur des cas" et le "pire des cas" complexités?

C'est probablement le plus clairement illustrée par des exemples.Par exemple, si nous utilisons la recherche linéaire pour trouver un nombre dans un tableau trié puis l' pire des cas c'est quand nous décidons de recherche pour le dernier élément la matrice comme cela prendrait autant d'étapes qu'il y a d'éléments dans le tableau.L' dans le meilleur des cas lorsque l'on recherche la premier élément depuis que nous avons faites après le premier contrôle.

Le point de toutes ces adjectif-la complexité, c'est que nous sommes à la recherche d'un moyen pour tracer le graphique de la quantité de temps un hypothétique programme s'exécute à la réalisation en termes de la taille de certaines variables.Cependant, pour de nombreux algorithmes, vous pouvez faire valoir qu'il n'existe pas une seule fois pour un particulier de la taille de l'entrée.Notez que ceci est en contradiction avec l'exigence fondamentale d'une fonction, n'importe quelle entrée doit pas avoir plus d'une sortie.Nous arrivons donc avec plusieurs les fonctions de décrire un algorithme de complexité.Maintenant, même si la recherche d'un tableau de taille n peut prendre plus ou moins de temps selon ce que vous cherchez dans le tableau et en fonction proportionnelle à n, nous pouvons créer des informations de description de l'algorithme en utilisant le meilleur des cas, cas moyen, et de la pire des classes de cas.

Désolé, c'est tellement mal écrit et n'a pas beaucoup d'informations techniques.Mais j'espère que c'vais prendre le temps de la complexité des classes plus facile de réfléchir.Une fois que vous devenez à l'aise avec celles-ci, il devient une simple question de l'analyse par le biais de votre programme et à la recherche de choses comme des boucles qui dépendent de la taille des matrices et de raisonnement basé sur vos données de structures de ce type d'entrée en résulterait dans les cas triviaux et ce qui allait entraîner dans le pire des cas.

Je ne sais pas combien de programmation pour résoudre ce problème, mais la première chose que les gens font, c'est qu'on l'échantillon de l'algorithme pour certains modèles, le nombre d'opérations de fait, dire 4n^2 + 2n + 1 nous avons 2 règles:

Si nous avons une somme de termes, le terme avec le plus grand taux de croissance est maintenue, avec d'autres termes omis.
Si nous avons un produit de plusieurs facteurs facteurs constants sont omis.

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

Pour le code, la boucle externe seront exécutés pour n+1 fois, le " 1 " signifie le processus qui vérifie si j'ai encore répond à l'exigence.Et l'intérieur de la boucle est exécuté n fois, n-2 fois....Ainsi,0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

Pour le code B, si la boucle interne de ne pas intervenir et d'exécuter les foo(), à l'intérieur de la boucle sera exécutée n fois fonction de la boucle externe de l'exécution, qui est O(n)

Je voudrais expliquer le Big-O dans un peu d'aspect différent.

Big-O est juste pour comparer la complexité des programmes qui signifie à quelle vitesse ils sont en croissance quand les entrées sont en augmentation et ce n'est pas exactement l'heure de passer à l'action.

À mon humble avis dans le big-O formules vous feriez mieux de ne pas utiliser plus complexe des équations (vous pouvez il suffit de coller à ceux dans le graphique suivant.) Cependant, vous pouvez encore utiliser d'autres plus précis de la formule (3^n, n^3, ...), mais plus que cela peut être parfois trompeuses!Il est donc préférable de le garder aussi simple que possible.

Je tiens à souligner encore une fois que nous avons ici ne voulez pas d'obtenir une formule exacte pour notre algorithme.Nous voulons seulement montrer comment elle se développe quand les entrées sont en croissance et les comparer avec les autres algorithmes dans ce sens.Sinon, vous feriez mieux d'utiliser d'autres méthodes comme le bench-marking.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow