Qu'est-ce que Big O d'une boucle?
Que j'ai lu sur Big O notation. Il a déclaré,
Le grand O de boucle est le nombre d'itérations de la boucle en
le nombre d'instructions dans la boucle.
Voici un extrait de code,
for (int i=0 ;i<n; i++)
{
cout <<"Hello World"<<endl;
cout <<"Hello SO";
}
Maintenant selon la définition, le Big O doit être O(n*2) mais il est O(n). Quelqu'un peut-il m'aider en expliquant pourquoi est-ce?
Grâce à adavance.
Il est seulement à la n de l'itération de l'intérieur de la boucle
Mais il y a 2 instructions dans la boucle
voir ma réponse, les instructions dans la boucle de prendre à temps constant, deux constantes de faire une autre constante. Ce qui compte c'est le nombre d'itérations dans la boucle.
double possible de Plaine explication anglais de Big O
Pas de Pas de son Grand O O(n) comme nous allons avec équation du temps de la boucle est exécuté pour n+1 fois si grand O n pas n2..
Mais il y a 2 instructions dans la boucle
voir ma réponse, les instructions dans la boucle de prendre à temps constant, deux constantes de faire une autre constante. Ce qui compte c'est le nombre d'itérations dans la boucle.
double possible de Plaine explication anglais de Big O
Pas de Pas de son Grand O O(n) comme nous allons avec équation du temps de la boucle est exécuté pour n+1 fois si grand O n pas n2..
OriginalL'auteur Fahad Uddin | 2011-08-06
Vous devez vous connecter pour publier un commentaire.
Si vous cochez la définition de l'O() notation, vous verrez que l' (multiplicateur) constantes n'a pas d'importance.
Le travail à faire à l'intérieur de la boucle est pas 2. Il y a deux états, pour chacun d'eux vous avez à faire à un couple d'instructions machine, c'est peut-être 50, 78, ou que ce soit, mais c'est complètement hors de propos pour l'asymptotique de la complexité des calculs, car ils sont de toutes les constantes. Il ne dépend pas de
n
. C'est juste O(1).Yepp, merci pour la clarification.
OriginalL'auteur Karoly Horvath
O(n) est utilisé pour messure de la boucle de contre mathématique d'une fonction (comme n^2, n^m,..).
Donc si vous avez une boucle comme ceci
Le meilleur mathématiques décrivant la fonction de la boucle de prend est calculé en O(n) (où n est un nombre entre 0..infinity)
Si vous avez une boucle comme ceci
Signifie qu'il sera pris en O(n*2); fonction mathématique = n*2
Cette boucle prend O(n^2); mathématiques d'une fonction = n^n
De cette façon, vous pouvez calculer combien de temps votre boucle besoin pour n 10 ou 100 ou 1000
De cette façon, vous pouvez créer des graphiques pour des boucles et des.
OriginalL'auteur blejzz
Tout d'abord, ne pas l'appeler "le Grand O". C'est faux et trompeur. Ce que vous êtes vraiment essayer de trouver est asymptotiquement combien d'instructions sera exécuté comme une fonction de n. La bonne façon de penser à propos de O(n) n'est pas en fonction, mais plutôt comme un ensemble de fonctions. Plus précisément:
En d'autres termes, lorsque n devient très grand, à un certain point la croissance de la fonction (par exemple, le nombre d'instructions) sera délimitée ci-dessus par une fonction linéaire avec une constante coefficient.
Selon la façon de compter les instructions de la boucle peut exécuter un certain nombre de directives, mais peu importe ce qu'il ne itérer au plus n fois. Par conséquent, le nombre d'instructions est en O(n). Il n'a pas d'importance si elle se répète 6n ou .5n ou 100000000n fois, ou même si elle n'exécute qu'un nombre constant d'instructions! Il est encore dans la classe de fonctions en O(n).
D'étendre un peu plus, la classe de O(n*2) = O(0.1*n) = O(n), et la classe O(n) est strictement contenue dans la classe O(n^2). En conséquence, cette boucle est également en O(2*n) (car O(2*n) = O(n)), et contenue dans O(n^2) (mais ça à la limite supérieure n'est pas serré).
OriginalL'auteur Mikola
Big-O notation ignore les multiplicateurs constants par la conception (et par définition), on a donc O(n) et O(2n) est exactement la même chose. Nous avons l'habitude d'écrire des O(n), car c'est plus court et plus familier, mais O(2n) signifie la même chose.
OriginalL'auteur Henning Makholm
O(n) désigne la boucle du temps de la complexité augmente linéairement avec le nombre d'éléments.
2*n est toujours linéaire, donc, vous dites que la boucle est de l'ordre O(n).
Cependant, la boucle que vous avez posté est O(n) puisque les instructions dans la boucle de prendre à temps constant. Deux fois une constante est toujours une constante.
OriginalL'auteur Griffin
Généralement
big O
notation exprime le nombre des opérations principales dans une fonction.Dans ce tou êtes overating sur n éléments. Si la complexité est O(n).
N'est sûrement pas O(n^2), depuis quadratique est la complexité de ces algorithmes, comme dans une bulle de sorte que comparer chaque élément dans l'entrée avec tous les autres éléments.
Que vous vous en souvenez, le tri à bulles, afin de déterminer la position dans laquelle insérer un élément à, comparer chaque élément avec les autres n dans une liste (bouillonnement comportement).
Au plus, vous pouvez prétendre que vous êtes algorithme a une complexité O(2n),car il imprime en 2 phrases pour chaque élément dans l'entrée, mais dans
big O
la notation O(n) est quiv de O(2n).OriginalL'auteur user278064