J'apprends la notation Big-O et je travaille sur une mission sur laquelle je suis coincé. Fondamentalement, j'ai reçu différentes fonctions et je dois écrire le Big (O) pour elles. Je pense que ma confusion réside dans les fonctions qui peuvent être incluses dans Big-O. Je comprends la hiearchy comme suit: O (1) O (logn) O (n) O (nlogn) O (n ^ 2) O (2 ^ n) O (n!)

Je comprends aussi pourquoi les constantes et les termes plus petits sont laissés de côté, puisque nous cherchons simplement une borne. Ma question est ce qui se passe lorsqu'une fonction n'est pas écrite dans ces termes. Par exemple (ce n'est pas ma question exacte mais similaire), 3 ^ n n'est pas un multiple constant de 2 ^ n. Le Big-O est-il alors O (3 ^ n) ou encore O (2 ^ n)? Ma pensée est O (3 ^ n) car 3 ^ n croît plus vite que 2 ^ n et Big O est une borne supérieure. Mais je n'ai pas vu Big O exprimé avec une base qui n'est pas 2 ou n comme indiqué ci-dessus. Cette pensée est-elle correcte?

4
user8584662 9 sept. 2017 à 19:02

2 réponses

Quelles fonctions sont incluses dans Big-O Notation?

*


Cependant, certaines fonctions sont plus couramment utilisées, comme O(logn) que vous avez mentionnée par exemple. La raison en est la nature des problèmes que nous tentons de résoudre avec la plupart des algorithmes (comme le tri par exemple), ce qui nous permet d'utiliser certaines fonctions comme limites supérieures plus fréquemment que d'autres.


PS: Plus précisément, c'est une liste de classes, où n atteint asymptotiquement Infinity. Pour en savoir plus, lisez Ordre des fonctions.

4
gsamaras 9 sept. 2017 à 16:18

Formellement f(x) = O(g(x)) si et seulement s'il existe des constantes c>0 et n>0 telles que:

c*g(x) > f(x) pour tout x supérieur ou égal à n.

Avec cette définition à l'esprit, vous pouvez brancher n'importe quelle fonction dans le O et vous obtiendrez un ensemble de fonctions satisfaisant la propriété.

Une autre façon d'y penser est de définir O comme une fonction allant de fonctions à des ensembles de fonctions. C'est-à-dire O(g) = { f : c*g(x) >= f(x) for all x > n} pour les constantes c et n comme décrit ci-dessus. En utilisant cette définition, on dirait f est dans O(g) ce que IMHO a beaucoup plus de sens, mais nous sommes coincés avec la notation utilisant le signe égal pour des raisons historiques.

Maintenant, en regardant la définition, nous pouvons comprendre la hiérarchie que vous mentionnez. O(n^2) vient après O(n) parce que n = O(n^2) est vrai mais n^2 = O(n) est faux (notez encore que je n'utilise pas! = Comme ça = le signe dans la notation O n'est pas un vrai égal mais un symbole syntaxique arbitraire que vous pourriez aussi bien remplacer par une rune naine).

Autre chose, si vous voulez tricher dans votre devoir, répondez simplement O(n!) pour tout et vous serez techniquement correct (le meilleur type de correct). Maintenant, généralement quand les gens demandent «quel ordre est cette fonction», ils demandent une borne serrée, c'est la plus petite fonction croissante qui agira toujours comme une borne. Vous pouvez également consulter les définitions d'autres notations associées.

0
jspurim 14 sept. 2017 à 16:37