Big O, comment calculez-vous/approximatif?
La plupart des gens avec un diplôme en CS savez certainement ce que Big O est synonyme de.
Il nous aide à mesurer le degré de (in)efficace, un algorithme est vraiment et si vous savez dans dans quelle catégorie le problème que vous essayez de résoudre réside dans, que vous pouvez découvrir si il est encore possible de faire sortir le petit plus de performance.1
Mais je suis curieux, comment faire vous calculer ou approximative de la complexité des algorithmes de votre?
1 mais comme ils le disent, n'en abusez pas, l'optimisation prématurée est la racine de tous les maux, et l'optimisation sans cause justifiée faut mériter ce nom.
Peut-être que vous n'avez pas réellement besoin pour améliorer votre algorithme de complexité, mais vous devriez au moins être en mesure de calculer, pour décider...
J'ai trouvé cette explication claire de Big O, Gros Omega, et les Grandes Thêta: xoax.net/comp/sci/algorithms/Lesson6.php
-1: Soupir, un autre abus de BigOh. BigOh est juste un asymptotique limite supérieure et pourrait être utilisé pour quoi que ce soit et n'est pas seulement CS liés. Parler BigOh comme si il y en a un unique est vide de sens (Un temps linéaire algorithme est O(n^2), O(n^3), etc). En disant cela nous aide mesure efficacité est trop trompeuse. Aussi, quel est le lien pour la complexité des classes? Si vous êtes intéressé, est des techniques pour calculer le temps d'exécution des algorithmes, comment est-ce pertinent?
Big-O ne mesure pas l'efficacité, et il mesure les performances d'un algorithme échelles avec la taille (il peut s'appliquer à d'autres choses que la taille est trop mais c'est ce qui nous intéresse ici) et que seulement asymptotiquement, donc si vous êtes hors de la chance un algorithme avec un "petit" big-O peut être plus lent (si le Big-O s'applique à des cycles) qu'un autre jusqu'à ce que vous atteindre un très grand nombre.
Le choix d'un algorithme sur la base de son Grand-O complexité est généralement une partie essentielle de la conception du programme. Il est très certainement pas un cas de "l'optimisation prématurée", qui en tout cas est tellement abusé de la citation sélective.
J'ai trouvé cette explication claire de Big O, Gros Omega, et les Grandes Thêta: xoax.net/comp/sci/algorithms/Lesson6.php
-1: Soupir, un autre abus de BigOh. BigOh est juste un asymptotique limite supérieure et pourrait être utilisé pour quoi que ce soit et n'est pas seulement CS liés. Parler BigOh comme si il y en a un unique est vide de sens (Un temps linéaire algorithme est O(n^2), O(n^3), etc). En disant cela nous aide mesure efficacité est trop trompeuse. Aussi, quel est le lien pour la complexité des classes? Si vous êtes intéressé, est des techniques pour calculer le temps d'exécution des algorithmes, comment est-ce pertinent?
Big-O ne mesure pas l'efficacité, et il mesure les performances d'un algorithme échelles avec la taille (il peut s'appliquer à d'autres choses que la taille est trop mais c'est ce qui nous intéresse ici) et que seulement asymptotiquement, donc si vous êtes hors de la chance un algorithme avec un "petit" big-O peut être plus lent (si le Big-O s'applique à des cycles) qu'un autre jusqu'à ce que vous atteindre un très grand nombre.
Le choix d'un algorithme sur la base de son Grand-O complexité est généralement une partie essentielle de la conception du programme. Il est très certainement pas un cas de "l'optimisation prématurée", qui en tout cas est tellement abusé de la citation sélective.
OriginalL'auteur sven | 2008-08-06
Vous devez vous connecter pour publier un commentaire.
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 peuvent être utilisés pour obtenir la BigOh.
Comme un "livre de cuisine", afin d'obtenir la BigOh à partir d'un morceau de code, vous devez d'abord réaliser que vous êtes la création d'une formule math pour compter le nombre d'étapes de calculs exécutés donné une entrée de taille.
Le but est simple: pour comparer les algorithmes à partir d'un point de vue théorique, sans la nécessité d'exécuter le code. Le moindre le nombre d'étapes, le plus rapide de l'algorithme.
Par exemple, disons que vous avez ce morceau de code:
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:
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:Le paramètre
N
prend ladata.length
valeur. Maintenant, nous avons besoin de la définition de la fonctionf()
. 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.Qui signifie que les lignes 1 et 4 prend C nombre de mesures de chaque, et la fonction est un peu comme ceci:
La partie suivante est de définir la valeur de la
for
déclaration. Rappelez-vous que l'on compte le nombre d'étapes de calcul, ce qui signifie que le corps de lafor
instruction est exécutéeN
fois. C'est le même que l'ajout deC
,N
fois: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 lafor
déclaration.D'obtenir le véritable BigOh nous avons besoin de la L'analyse asymptotique de la fonction. C'est à peu près comme ceci:
C
.f()
obtenir le polynomium dans sonstandard form
.N
approchesinfinity
.Notre
f()
a deux termes:Emportant tous les
C
constantes et les parties redondantes:Depuis le dernier terme est celui qui grandit quand
f()
approche de l'infini (pensez à limites) c'est le BigOh argument, et lasum()
de la fonction de la BigOh de:Il y a quelques astuces pour résoudre des problèmes: l'utilisation sommations chaque fois que vous le pouvez.
Comme un exemple, ce code peut être facilement résolu en utilisant des sommations:
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'êtreO(1)
, vous devez demander à vos professeurs à ce sujet.O(1)
les moyens (ou presque, la plupart du temps) constanteC
, indépendant de la tailleN
.La
for
déclaration sur le nombre de phrase est délicat. Alors que l'indice se termine à2 * N
, l'incrémentation se fait par deux. Cela signifie que la premièrefor
est exécuté seulementN
étapes, et nous avons besoin de diviser le nombre par deux.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èmefor
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èmefor
n'est jamais exécuté.Sur la formule, ce qui signifie:
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.
(Nous supposons que
foo()
estO(1)
et prendC
étapes).Nous avons un problème ici: quand
i
prend la valeurN /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 momenti
prendN /2 + 1
.Depuis le moment central
i > N /2
, à l'intérieurfor
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é:
w
)L'application à l'algèbre:
Et la BigOh est:
Il dépend. C'est
O(n)
oùn
est le nombre d'éléments, ouO(x*y)
oùx
ety
sont les dimensions de la matrice. Grand-oh est "relative à l'entrée", donc, cela dépend de ce qui est à votre entrée.Grande réponse, mais je suis vraiment coincé. Comment ne Somme(i de 1 à N / 2)( N ) se transforme en ( N ^ 2 / 2 ) ?
En règle générale, la somme(i de 1 à (a) (b) a * b. C'est juste une autre façon de dire: b+b+...(un temps)+b = a * b (par définition pour certaines définitions de l'entier de la multiplication).
Pas tellement pertinent, mais juste pour éviter la confusion, il y a une petite erreur dans cette phrase: "l'indice i prend les valeurs: 0, 2, 4, 6, 8, ..., 2 * N". De l'Index j'ai fait va jusqu'à 2 * N - 2, la boucle va s'arrêter alors.
OriginalL'auteur vz0
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
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.
Si nous voulions trouver un numéro dans la liste:
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:
C'est O(n^2), car à chaque passage de la boucle externe ( O(n) ), nous devons aller par le biais de l'ensemble de la liste de nouveau de sorte que le n de se multiplier, nous laissant avec n au carré.
C'est à peine de gratter la surface, mais quand vous arrivez à l'analyse plus complexe des algorithmes mathématiques complexes impliquant des preuves entre en jeu. Espérons que cela aide à vous familiariser avec les notions de base au moins.
Pas vraiment, un aspect qui conduisent à la n au carré temps sera considéré comme n^2
Vous n'aurez pas toujours la boucle imbriquée, comme les appels de fonctions peuvent ne >
O(1)
travail eux-mêmes. Dans le C Api standard par exemple,bsearch
est intrinsèquementO(log n)
,strlen
estO(n)
, etqsort
estO(n log n)
(techniquement, il n'a pas de garanties, et quicksort lui-même a un pire des cas, la complexité deO(n²)
, mais en supposant que votrelibc
auteur n'est pas un crétin, à la moyenne de la complexité de l'affaire estO(n log n)
et il utilise un pivot stratégie de sélection qui réduit les chances de toucher leO(n²)
cas). Et les deuxbsearch
etqsort
peut être pire si le comparateur de fonction est pathologique.OriginalL'auteur DShook
Tout en sachant comment comprendre le Big O moment pour votre problème particulier est utile, sachant que certains cas peuvent aller un long chemin en vous aidant à prendre des décisions dans votre algorithme.
Ici sont quelques-uns des cas les plus courants, levée de http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:
O(1) - Déterminer si un nombre est pair ou impair; l'utilisation d'une taille constante recherche de table ou table de hachage
O(logn) - la recherche d'un élément dans un tableau trié avec une recherche binaire
O(n) - la recherche d'un élément dans une liste non triée; l'ajout de deux n-chiffres
O(n2) - Multiplication de deux n-chiffres par un algorithme simple; l'ajout de deux n×n matrices; tri à bulles ou le tri par insertion
O(n3) - Multiplication de deux n×n matrices par un algorithme simple
O(cn) - 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(nn), Souvent utilisé au lieu de O(n!) pour dériver des formules plus simples pour asymptotique de la complexité
Pourquoi ne pas utiliser
x&1==1
pour vérifier la bizarrerie?Ce serait une manière typique pour vérifier (en fait, juste des tests
x & 1
serait suffisant, pas besoin de vérifier== 1
; en C,x&1==1
est évaluée commex&(1==1)
grâce à la priorité de l'opérateur, c'est donc en fait le même que le testx&1
). Je pense que vous êtes la lecture de la réponse; il y a un point-virgule, pas une virgule. Il ne dit pas: vous auriez besoin d'une table de recherche pour les paires/impaires de test, c'est à dire à la fois pair/impair de test et contrôle d'une table de recherche sontO(1)
opérations.Mot. Véritable point.
OriginalL'auteur Giovanni Galbo
Petit rappel: le
big O
notation est utilisée pour désigner asymptotique complexité (c'est à dire lorsque la taille du problème augmente à l'infini), et, se cache une constante.Ce qui signifie qu'entre un algorithme en O(n) et une en O(n2), de la manière la plus rapide n'est pas toujours le premier (bien qu'il existe toujours une valeur de n telle que pour des problèmes de taille >n, le premier algorithme est plus rapide).
Noter que le caché de la constante dépend très largement de la mise en œuvre de!
Aussi, dans certains cas, l'exécution n'est pas une fonction déterministe de la taille n de l'entrée. Prendre le tri à l'aide de 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:
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.OriginalL'auteur OysterD
À 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, la maître de la méthode que nous avons pensé à l'université.
Avec 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 calculer.
Je voudrais également ajouter comment cela est fait pour fonctions récursives:
supposons que nous avons une fonction comme (schéma de code):
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 de performance pour le corps est: O(1) (constante).
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 de performance pour les appels récursifs est: O(n-1) (commande 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 non 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.
+1 pour la récursivité... Aussi c'est beau: "...même le professeur nous a encouragés à penser..." 🙂
Oui, c'est tellement bon. J'ai tendance à penser comme cela , plus le terme à l'intérieur de O(..) , de plus le travail que vous êtes / machine est en train de faire. La pensée tout en se rapportant à quelque chose pourrait être une approximation , mais qui sont donc ces limites. Ils ont juste vous dire comment le travail à faire augmente lorsque le nombre d'entrées augmente.
OriginalL'auteur sven
Si le 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.:
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:
OriginalL'auteur Marcelo Cantos
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 journal2 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.
Tellement de 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.
Pour ce que ça vaut, je a écrit un livre revêtement et d'autres sujets. Il a depuis longtemps épuisé, mais les exemplaires sont en cours pour un prix raisonnable. J'ai essayé de m'GoogleBooks à l'attraper, mais pour le moment c'est un peu dur à comprendre, qui a eu le droit d'auteur.
OriginalL'auteur Mike Dunlavey
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)
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 dela diminution avec l' -> opérateur).
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)
temps, qui est, dans certains temps constant indépendant de l'entrée. Ces simples comprennentl'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
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ù 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, on peut 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:
Nous savons que ligne (1) prend
O(1)
temps. Clairement, nous faisons le tour de la boucle n fois, commenous 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
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 i < 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
i < 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)
de temps de fonctionnement.Un exemple.
OriginalL'auteur ajknzhol
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.
Ce qui 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.
Salut, belle réponse. Je me demandais si vous étiez au courant de toute bibliothèque ou à la méthodologie (je travaille avec python/R par exemple) afin de généraliser cette méthode empirique, sens comme raccord divers complexité des fonctions à l'augmentation de la taille du jeu de données, et de savoir ce qui est pertinent. Merci
OriginalL'auteur John D. Cook
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...)
OriginalL'auteur Adam
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.
OriginalL'auteur Lasse Vågsæther Karlsen
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.
Puisque 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 cet). 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)).
Cependant, Big O cache quelques détails qui parfois nous ne pouvons pas ignorer. Envisager le calcul de la suite de Fibonacci avec
et vous permet de simplement supposer que 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!
Vous ne devriez pas vous souciez de la façon dont les nombres sont enregistrés, il ne change pas que l'algorithme progresse à un upperbound de O(n).
OriginalL'auteur
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 la documentation ou même IntelliSense.
OriginalL'auteur Matt Mitchell
Moins utile en général, je pense, mais par souci d'exhaustivité, il est aussi 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.
OriginalL'auteur Martin
Comme "comment voulez-vous calculer le" Big O, c'est en partie 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.
OriginalL'auteur Suma
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 pouri
allant de0
àn-1
(à cause de la baisse de, pas inférieur ou égal) de lan-i
. Vous obtenez finalementn*(n + 1) /2
, doncO(n²/2) = O(n²)
.Pour la 2ème boucle,
i
est entre0
etn
inclus pour la boucle externe; ensuite, la boucle interne est exécutée lorsquej
est strictement supérieur àn
, ce qui est impossible.OriginalL'auteur Emmanuel
En outre à 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.
OriginalL'auteur Eric
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.
OriginalL'auteur JB King
Ce qui est souvent négligée, est le devrait 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. . .."
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.
OriginalL'auteur Baltimark
grande question!
Avertissement: cette réponse contient de fausses déclarations, voir les commentaires ci-dessous.
Si vous utilisez le 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.
Découvrez ce site pour une belle définition formelle de Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html
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 le pire des cas est lorsque nous décidons de de recherche pour le dernier élément de la matrice comme cela prendrait autant d'étapes qu'il y a d'éléments dans le tableau. Le meilleur des cas serait 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 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.
C'est une idée fausse commune que big-O désigne le pire des cas. Comment faire O et Ω concernent le pire et le meilleur des cas?
C'est trompeur. Big-O signifie que la limite supérieure pour une fonction f(n). Omega moyens de limite inférieure pour une fonction f(n). Il n'est pas du tout liées à meilleur des cas ou le pire des cas.
Vous pouvez utiliser le Big-O comme une limite supérieure pour le meilleur ou le pire des cas, mais d'autres que, oui aucun rapport.
OriginalL'auteur Samy Bencherif
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 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 [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 . . . .
OriginalL'auteur Gavriel Feria
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 s'exécuten
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)
OriginalL'auteur laynece
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 une fois de plus qu'ici nous ne nous en 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.
OriginalL'auteur HmT