Dupliqué possible:
Anglais ordinaire Explication de Big OJ'imagine que c'est probablement quelque chose d'enseigné dans des cours, mais comme je suis un programmeur autodidacte, je ne l'ai vu que rarement.
J'ai rassemblé que c'est quelque chose à faire avec le temps, et o (1) est le meilleur, tandis que des choses comme O (n ^ n) sont très mauvaises, mais quelqu'un pourrait-il me dire une explication fondamentale de ce qu'il représente en fait et où ces chiffres viennent de?
3 Réponses :
Big O fait référence au pire des cas d'ordre d'exécution. Il est utilisé pour montrer comment bien une balance d'algorithme basée sur la taille de l'ensemble de données (N-> Nombre d'éléments).
Puisque nous ne sommes concernés que par la commande, les multiplicateurs constants sont ignorés et tous les termes qui augmentent moins rapidement que le terme dominant sont également supprimés. Quelques exemples:
Une seule opération ou ensemble d'opérations est O (1), car il faut une certaine heure constante (ne varie pas en fonction de la taille du jeu de données).
Une boucle est O (n). Chaque élément de l'ensemble de données est enroulé sur.
Une boucle imbriquée est O (n ^ 2). Une boucle imbriquée imbriquée est O (n ^ 3), et vers l'avant.
Des choses comme la recherche d'arbres binaires sont du journal (n), qui est plus difficile à montrer, mais à tous les niveaux de l'arborescence, le nombre possible de solutions est réduit de moitié. Le nombre de niveaux est donc logiciel (n) (à condition que le L'arbre est équilibré).
Quelque chose comme trouver la somme d'un ensemble de chiffres le plus proche d'une valeur donnée est O (n!), car la somme de chaque sous-ensemble doit être calculée. C'est très mauvais.
Vous pouvez également utiliser cette note pour décrire le comportement spatial.
-1 n'a pas besoin d'être pires cas, dans la classe d'algorithmes de la dernière année, nous avons montré le Big O pour le pire des cas, le meilleur cas, et si nous pouvions le comprendre, cas moyen.
Souvent grosse notation est une affaire moyenne. Nous disons que la recherche d'interpolation est O (journal de journal n), mais c'est le pire des cas est O (n) si les valeurs sont assez éloignées. en.wikipedia.org/wiki/interpolation_search
Big O est parfois utilisé pour montrer des cas plus courants depuis le pire des cas, ce n'est pas si intéressant. Si vous voyez O (n ^ 2) sans aucune mises en garde, vous devez assumer le pire des cas. Secure.wikimedia.org/wikipedia/fr/wiki/...
C'est une façon d'exprimer la complexité du temps.
O (n) signifie pour n éléments dans une liste, il prend n calcul pour trier la liste. Ce qui n'est pas mauvais du tout. Chaque augmentation de N augmente la complexité de temps linéairement.
O (n ^ n) est mauvais, car la quantité de calcul requise pour effectuer une sorte (ou tout ce que vous faites) augmente exponentiellement lorsque vous augmentez n .
O (1) est le meilleur, car cela signifie 1 calcul pour effectuer une fonction, penser aux tables de hachage, la recherche d'une valeur dans une table de hachage contient O (1) < / Code> Complexité du temps.
En fait, ce n'est pas tout à fait raison. Il s'agit d'exprimer le taux dans lequel les coûts les plus graves augmentent. SO O (N) signifie que si le nombre d'éléments de données en cours de traitement double le pire des cas pour le traitement des données doublera. Oh et et o (1) ne signifie pas "1 calcul", cela signifie que les coûts de calcul sont constants, quel que soit le nombre de points de données. Une table de hachage sans collision n'est pas un bon exemple.
Big O notation appliquée à un algorithme fait référence à la manière dont le temps d'exécution de l'algorithme dépend de la quantité de données d'entrée. Par exemple, un algorithme de tri prendra plus de temps pour trier un ensemble de données volumineux que d'un petit ensemble de données. Si pour l'exemple de tri des algorithmes, vous graphiquez le temps d'exécution (axe vertical) vs le nombre de valeurs à trier (axe horizontal), pour un nombre de valeurs de zéro à un grand nombre, la nature de la ligne ou de la courbe que les résultats obtiendront dépendent de l'algorithme de tri utilisé. Big O notation est une méthode abrégée pour décrire la ligne ou la courbe.
Dans la grosse notation, l'expression entre crochets est la fonction graphique. Si une variable (dire n) est incluse dans l'expression, cette variable fait référence à la taille du jeu de données d'entrée. Vous dites O (1) est le meilleur. Ceci est vrai parce que le graphique f (n) = 1 ne varie pas avec n. Un algorithme O (1) prend la même quantité de temps à compléter indépendamment de la taille du jeu de données d'entrée. En revanche, le temps d'exécution d'un algorithme de O (n ^ n) augmente avec le carré de la taille de l'ensemble de données d'entrée.
C'est l'idée de base, pour une explication détaillée, consultez la page Wikipedia intitulée «Big O Notation».
Dupliquer