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


La plupart des personnes avec un diplôme en CS sauront certainement ce que Big O est synonyme de. Cela nous aide à mesurer à quel point un algorithme est efficace et si vous le savez quelle catégorie le problème que vous essayez de résoudre réside dans vous pouvez déterminer s'il est encore possible de réduire cette petite performance supplémentaire.1

Mais je suis curieux, comment faire toi calculer ou approximer 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 Malet l'optimisation sans cause justifiée devrait également mériter ce nom.


784
2017-08-06 10:18


origine


Réponses:


Je suis un assistant de professeur à mon université locale sur le cours de structures de données et d'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 le 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 procédure mécanique cela peut être utilisé pour obtenir le BigOh.

En tant que "livre de cuisine", pour obtenir BigOh à 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 pour une entrée de 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 de pas 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 somme de tous les éléments du tableau, et nous voulons créer une formule pour compter le complexité de calcul de cette fonction:

Number_Of_Steps = f(N)

Donc nous avons 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 telle que:

Number_Of_Steps = f(data.length)

Le paramètre N prend le data.length valeur. Maintenant, nous avons besoin de la définition actuelle de la fonction f(). Ceci est 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 point, nous allons supposer que chaque phrase qui ne dépend pas de la taille des données d'entrée prend une constante C nombre de pas de calcul.

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

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

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

La partie suivante consiste à définir la valeur de for déclaration. Rappelez-vous que nous comptons le nombre d'étapes de calcul, ce qui signifie que le corps de la for déclaration est exécutée N fois. C'est la même chose que d'ajouter C, 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 de la for est exécuté, vous devez le compter en regardant ce que fait le code. Pour simplifier les calculs, nous ignorons les parties d'initialisation, de condition et d'incrément de la variable for déclaration.

Pour obtenir le BigOh réel, nous avons besoin de la Analyse asymptotique de la fonction. Ceci est à peu près fait comme ceci:

  1. Enlève toutes les constantes C.
  2. De f() obtenir le polynome dans son standard form.
  3. Diviser les termes du polynôme et les trier par le taux de croissance.
  4. Gardez celui qui grossit quand N approches infinity.

Notre f() a deux termes:

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

Enlevant tous les C constantes et parties redondantes:

f(N) = 1 + N ^ 1

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

O(N)

Il y a quelques astuces pour résoudre certains problèmes: utiliser sommations quand 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 à vous demander est l'ordre d'exécution de foo(). Alors que l'habituel est d'être O(1), vous devez demander à vos professeurs à ce sujet. O(1) signifie (presque, presque) constante C, indépendant de la taille N.

le for déclaration sur la phrase numéro un est difficile. 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)( ... )

Le numéro de la phrase deux est encore plus délicat car cela 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 la seconde for s'exécute: N fois le premier, N - 2 le deuxième, N - 4 le troisième ... jusqu'au stade N / 2, sur lequel le second for jamais exécuté.

Sur la formule, cela signifie:

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

Encore une fois, nous comptons le nombre de marches. Et par définition, chaque sommation devrait toujours commencer à un, et se terminer à 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 pas.)

Nous avons un problème ici: quand i prend la valeur N / 2 + 1 vers le haut, la sommation intérieure se termine à un nombre négatif! C'est impossible et faux. Nous devons diviser la sommation en deux, étant le point pivot du 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 charnière i > N / 2, l'intérieur 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 en utilisant certaines règles d'identité:

  1. Sommation (w de 1 à N) (C) = N * C
  2. Summation (w de 1 à N) (A (+/-) B) = Summation (w de 1 à N) (A) (+/-) Summation (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. Sommation (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 est:

O(N²)

1390
2018-01-31 15:33



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

Quelques exemples de la façon dont il est utilisé 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) puisque 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) puisque tout au plus nous aurions à 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 le premier essai et parcourir la boucle une fois parce que Big-O décrit la limite supérieure d'un algorithme (omega est pour la limite inférieure et theta pour la borne étroite) .

Lorsque nous arrivons à des 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 à nouveau parcourir toute la liste pour que les n se multiplient en nous laissant n au carré.

Cela ne fait que gratter la surface, mais quand vous arrivez à analyser des algorithmes plus complexes, des calculs complexes impliquant des preuves entrent en jeu. J'espère que cela vous familiarise avec les bases au moins cependant.


190
2017-08-06 13:34



Bien qu'il soit utile de savoir comment déterminer le moment idéal de votre problème, sachant que certains cas généraux peuvent vous aider à prendre des décisions dans votre algorithme.

Voici quelques-uns des cas les plus courants, levé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 recherche de taille constante ou une table de hachage

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

O (n) - Trouver un article dans une liste non triée; ajouter deux numéros à n chiffres

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

Sur3) - Multiplier 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 énoncés logiques sont équivalents en utilisant la force brute

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

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


87
2017-09-05 19:09



Petit rappel: le big O la notation est utilisée pour désigner asymptotique la complexité (c'est-à-dire lorsque la taille du problème croît à l'infini), et il cache une constante.

Cela signifie qu'entre un algorithme dans O (n) et un dans O (n2), 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 la mise en œuvre!

De plus, dans certains cas, le temps d'exécution n'est pas une fonction déterministe du Taille n de l'entrée. Prenez le tri en utilisant le 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érentes complexités temporelles:

  • 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 tu dis, premature optimisation is the root of all evilet (si possible) profilage devrait toujours être utilisé lors de l'optimisation du code. Cela peut même vous aider à déterminer la complexité de vos algorithmes.


40
2017-08-23 20:43



Voyant les réponses ici, je pense que nous pouvons conclure que la plupart d'entre nous en effet approcher l'ordre de l'algorithme par regarder et utilisez le bon sens au lieu de le calculer avec, par exemple, le méthode maître comme on pensait à l'université. Cela dit, je dois ajouter que même le professeur nous a encouragés (plus tard) à réellement pense à ce sujet au lieu de simplement le calculer.

Je voudrais aussi ajouter comment cela est fait pour fonctions récursives:

supposons que nous avons 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 pour le corps de la fonction seulement dans ce cas, rien de spécial n'est fait dans le corps, juste une multiplication (ou le retour de la valeur 1).

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

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

Alors le la performance pour les appels récursifs est: O (n-1) (l'ordre est n, comme nous jetons les parties insignifiantes).

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

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


Peter, répondre vos problèmes soulevés; la méthode que je décris ici gère réellement cela assez bien. Mais gardez à l'esprit que c'est toujours un approximation et pas une réponse mathématiquement correcte complète. La méthode décrite ici est aussi 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 de fonctionnement du corps de la fonction et le nombre d'appels récursifs, mais cela est tout aussi vrai pour les autres méthodes.


26
2017-08-07 08:10



Si votre coût est un polynôme, gardez simplement le terme 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, attention. 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 (journal N) <O (N) <O (N bûche N) <O (N2) <O (Nk) <O (en) <O (n!)


25
2018-01-31 13:30



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 de leur entropie. L'entropie d'un point de décision est la moyenne des informations 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 nombre de branches.2 de la probabilité inverse de cette branche. C'est ce que vous apprenez en exécutant cette décision.

Par exemple, un if déclaration 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 cherchiez une table de N objets, comme N = 1024. C'est un problème de 10 bits car log (1024) = 10 bits. Donc, si vous pouvez le rechercher avec des déclarations 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 faites 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. 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 appris très peu! 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 dans le nombre de bits que vous devez apprendre.

Supposons que vous faites de l'indexation. Supposons que la table soit pré-triée dans un grand nombre de cases, et que vous utilisiez certains des 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 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 l'indexation de la recherche est rapide.

Maintenant, pensez à trier. Vous avez N objets, 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 vraisemblables prennent tous des étapes O (N log N). Un algorithme de tri O (N) est possible s'il est basé sur une recherche d'indexation.

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


19
2018-03-10 13:24



Commençons depuis le début.

Tout d'abord, accepter le principe que certaines opérations simples sur les données peuvent être faites dans O(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. Structure accédant à des opérations (par exemple, l'indexation de tableau comme A [i], ou un pointeur descendre avec l'opérateur ->).
  5. Affectation simple telle que la copie d'une valeur dans une variable.
  6. Appels à des fonctions de 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, seulement une ou deux instructions sont nécessaires. En conséquence, plusieurs types d'instructions dans C peuvent être exécutées dans O(1) temps, c'est-à-dire dans une quantité de temps constante et indépendante de l'entrée. Ces simples comprennent

  1. Les instructions d'affectation qui n'impliquent pas d'appels de fonction dans leurs expressions.
  2. Lisez les déclarations.
  3. Écrire des instructions qui ne nécessitent pas d'appels de fonction pour évaluer les arguments.
  4. Les instructions de saut rompent, continuent, goto et retournent expression, où L'expression ne contient pas d'appel de fonction.

En C, de nombreuses for-loops sont formées en initialisant une variable d'index à une certaine valeur et incrémenter cette variable de 1 à chaque fois autour de la boucle. La boucle de fin se termine quand 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 par 1 à chaque fois autour de la boucle, et les itérations arrête quand j'atteins n - 1.

Cependant, pour le moment, concentrez-vous sur la forme simple de la boucle for- différence entre les valeurs finales et initiales, divisée par la quantité par laquelle la variable d'index est incrémentée nous dit 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 de saut; 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 quand i atteint n-1, la boucle s'arrête et aucune itération ne se produit avec i = n-1), et 1 est ajouté à 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 par le nombre de fois autour de la boucle. Strictement parlant, nous devons alors ajouter O (1) heure pour initialiser l'indice de boucle et O (1) temps pour la première comparaison de l'indice de boucle avec le limite, parce que nous testons une fois de plus que nous faisons le tour de la boucle. Cependant, à moins il est possible d'exécuter la boucle zéro fois, le temps d'initialiser la boucle et tester la limite est une fois 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 que ligne 1) prend O(1) temps. De toute évidence, nous faisons le tour de la boucle n fois, comme nous pouvons déterminer en soustrayant la limite inférieure de la limite supérieure trouvée en ligne (1) puis en ajoutant 1. Puisque le corps, la ligne (2), prend O (1), nous pouvons négliger le temps pour incrémenter j et le temps pour comparer j avec n, qui sont aussi O (1). Ainsi, le temps de parcours des lignes (1) et (2) est le produit de n et O (1), lequel est O(n).

De même, nous pouvons limiter le temps de fonctionnement de la boucle extérieure constituée 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 des lignes (3) et (4) prend le temps O (n). Ainsi, on peut 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 le temps O (n).

L'initialisation i = 0 de la boucle externe et le (n + 1) st test de la condition Je prends aussi O (1) fois et peut être négligé. Enfin, nous observons que nous allons autour de la boucle externe n fois, en prenant O (n) temps pour chaque itération, donnant un total O(n^2) temps de course.


Un exemple plus pratique.

enter image description here


17
2018-02-02 15:30



Si vous voulez estimer empiriquement l'ordre de votre code plutôt que d'analyser le code, vous pouvez coller une série de valeurs croissantes de n et de temps pour votre code. Tracer vos horaires 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 par rapport à l'étude du code. D'une part, vous pouvez voir si vous êtes dans la plage où le temps d'exécution se rapproche de son ordre asymptotique. En outre, vous pouvez trouver que du code que vous pensiez être un ordre O (x) est vraiment un ordre O (x ^ 2), par exemple, en raison du temps passé dans les appels de bibliothèque.


11
2017-12-11 20:49



Fondamentalement, la chose qui revient 90% du temps est juste l'analyse des boucles. Avez-vous des boucles imbriquées simples, doubles ou triples? 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 bibliothèque de base étendue (comme par exemple, le .NET BCL ou le STL de C ++), vous rencontrerez tout ce qui est plus difficile que de simplement regarder vos boucles (pour les instructions, while, goto, etc...)


9
2017-08-14 15:35