Je lis un manuel pour ma classe Java III. Nous lisons à propos de Big-Oh et je suis un peu confus par sa définition formelle.
Définition formelle: "Une fonction f (n) est d'ordre à la plupart des g (n) - c'est-à-dire, f (n) = o (g (n)) - si un nombre réel positif C et un entier positif n existent telle que f (n) <= cg (n) pour tous n> = N. c'est-à-dire que cg (n) est une limite supérieure de F (n) lorsque n est suffisamment grande. "
OK, cela a du sens. Mais tenez-vous, continuez à lire ... le livre m'a donné cet exemple:
"dans le segment 9.14, nous avons dit qu'un algorithme qui utilise des opérations 5N + 3 est sur). Nous pouvons maintenant montrer que 5n + 3 = O (n) en utilisant la définition formelle de Big Oh.
Quand n> = 3, 5n + 3 <= 5n + n = 6n. Ainsi, si nous laissons F (n) = 5n + 3, g (n) = n, c = 6, n = 3, nous avons montré que f (n) <= 6 g (n) pour n> = 3 ou 5n + 3 = Au). C'est-à-dire si un algorithme nécessite du temps directement proportionnel à 5n + 3, c'est O (n). "
OK, ce genre de sens pour moi. Ils disent que si n = 3 ou plus, 5n + 3 prend moins de temps que si N était inférieur à 3 - Ainsi, 5n + n = 6n - droite? est logique, car si N était de 2 , 5n + 3 = 13 tandis que 6N = 12 mais lorsque N est 3 ou plus 5n + 3 sera toujours inférieur ou égal à 6n.
Voici où je suis confus. Ils me donnent un autre exemple: Exemple 2: "Montrons que 4N ^ 2 + 50N - 10 = O (n ^ 2). Il est facile de voir que: 4n ^ 2 + 50n - 10 <= 4n ^ 2 + 50N Pour tout n. Depuis 50n <= 50n ^ 2 pour n
= 50, 4n ^ 2 + 50n - 10 <= 4n ^ 2 + 50n ^ 2 = 54n ^ 2 pour n> = 50. Ainsi, avec C = 54 et N = 50, nous avons montré que 4N ^ 2 + 50n - 10 = O (n ^ 2). "
Cette déclaration n'a pas de sens: 50n <= 50n ^ 2 pour N> = 50.
n'est-ce pas de ne pas faire le 50n moins de 50n ^ 2? Pas seulement supérieur ou égal à 50? Pourquoi ont-ils même mentionné que 50n <= 50n ^ 2? Qu'est-ce que cela a à voir avec le problème?
Aussi, 4n ^ 2 + 50n - 10 <= 4n ^ 2 + 50n ^ 2 = 54n ^ 2 pour n> = 50 va être vrai, quoique n est.
Et comment dans le monde les chiffres de cueillette montrent que f (n) = O (g (n))?
5 Réponses :
n^2 <= 50n^2 for n >= 50
Peut-être que je suis mal compris le livre mais je lisais si n est un certain nombre, c'est 50 (50 ^ 2) et non 50 (50). 50 (50) n'est pas la même chose que 50 (50 ^ 2). Cela n'a jamais dit quoi que ce soit de substituer quoi que ce soit.
C'est juste une simple algèbre. Le seul terme que je travaille avec est celui sur le côté gauche. Tout ce que j'ai fait était montré que 50n = n ^ 2 si n = 50 .
Le tout sur la cueillette des chiffres n'est que ceci: pour faciliter la tâche. Parce que vous êtes autorisé à choisir tout numéro que vous aimez pour N et C, l'auteur choisit simplement quelque chose, où il est très facile de voir. Et c'est ce que vous pouvez également faire (lors de l'écriture d'un examen, etc.).
Donc, alors qu'il serait souvent possible d'utiliser un plus petit N, le raisonnement deviendrait un peu plus difficile (nécessitant souvent des connaissances antérieures sur l'analyse - nous avons tous appris des années auparavant, que X ne pousse pas aussi vite que x ^ 2 ... mais voulez-vous écrire la preuve d'analyse?)
Gardez-le simple, est le message :-) C'est un peu étrange pour s'y habituer au début.
Merci. Je comprends que je peux choisir n'importe quel nombre. Cependant, dans l'exemple que j'ai donné, l'auteur affirme que avec n'importe quel nombre> = 50 rend la déclaration 50n <= 50n ^ 2 vrai. Comment est-ce vrai? N'importe quel n fera cette déclaration vraie, pas seulement des chiffres> = 50. 50 (50) n'est pas la même chose que 50 (50 ^ 2), non?
De plus, il y a des pièces dans l'exemple où les chiffres semblent provenir de nulle part. Par exemple: l'auteur tente d'afficher 4n ^ 2 + 50n - 10 = O (n ^ 2). Plus tard, il écrit que 4N ^ 2 + 50n - 10 <= 4n ^ 2 + 50n ^ 2 = 54n ^ 2. Sur le côté droit, pourquoi décider-t-il soudainement de coller n ^ 2 devant le 50? Pourquoi les -10 ont-ils disparu sur le RHS?
1.: L'auteur a probablement pensé: pour n = 50, 50n <= 50n ^ 2 est identique que 50 * 50 <= 50 * 50 * 50 , dans lequel Cas, c'est super particulièrement facile à voir (mais vous voyez bien sûr, qu'il est également facile de voir pour tout N).
2: Si A , puis A , vous pouvez donc sauter le -10 . Similaire pour ajouter toute valeur positive (comme n ^ 2) sur le côté droit.
Merci. Ce que tu as dit a du sens pour moi. Surtout, cette première explication. Mais, je vois que nous pouvons choisir n'importe quel nombre mais pourquoi 50? Est-ce en quelque sorte plus difficile de prouver si le nombre est inférieur? Il semble juste que cela aurait plus de sens de dire quelque chose comme 50n <= 50n ^ 2 lorsque n> = 1 depuis que la déclaration est vraie pour tout numéro (positif).
@aloh: Ouais, je choisirais également N> = 1 Dans ce cas, car nous pouvons simplement annuler le 50n des deux côtés (car il est garanti d'être positif) et nous obtenions < Code> 1 <= n pour n> = 1. Mais c'est une question de goût.
Gardez à l'esprit que vous recherchez «une limite supérieure sur F (N) lorsque n est suffisamment grand». Ainsi, si vous pouvez montrer que f (n) est inférieur ou égal à certains c g (n) pour les valeurs de N supérieures à n, cela signifie que c g (n) est une limite supérieure de F (n) et F (n) La complexité de F (n) est donc O (g (n)).
Les exemples donnés sont destinés à montrer que la fonction donnée F (n) ne peut jamais se développer au-delà de C * G (N) pour tout N> N. en manipulant une limite supérieure initiale afin qu'elle puisse être exprimée plus simplement (si 4n ^ 2 + 50n est une limite supérieure sur f (n) puis de 4N ^ 2 + 50n ^ 2, qui est égale à 54n ^ 2, qui devient votre 54 * g (N) où c = 54 et G (n) = n ^ 2), les auteurs peuvent montrer que f (n) est délimité par C * G (N), qui a une complexité O (g (n)) et donc F (N).
Adrian merci. Lire à travers votre explication rendait tout beaucoup plus plus clair. Vous devriez être un enseignant!
Probablement la raison pour laquelle ils ont dit 50n = 50 est que si n est inférieur à 1, que n ^ 2 comme une analogie, si je dis «tous mes frères et sœurs parlent anglais», ce serait vrai, même s'il y a beaucoup de gens qui parlent anglais qui ne sont pas mes frères et sœurs. P> En ce qui concerne la preuve, nous pourrions le diviser en différentes déclarations. P> (1): 4n^2 + 50n - 10 <= 4n^2 + 50n (for all n)
(2): 4n^2 + 50n <= 4n^2 + 50n^2 (for all n>=50)
(3): 4n^2 + 50n^2 = 54 n^2 (for all n, including all n>=50)
(4): Therefore, 4n^2 + 50n - 10 <= 54n^2 for all n>=50
(5): Therefore, for f(n)=4n^2 + 50n - 10, g(n)=n^2, N=50, and c=54,
the statement f(n) <= c g(n) for all n >= N is true
(6): Therefore, by definition 4n^2 + 50n - 10=O(n^2).
Définition formelle:
Comme vous pouvez noter qu'il existe légèrement différent :)