Je pense avoir une bonne compréhension de ce que signifie la notation Big O, omega et thêta et comment prouver si une fonction est l'une d'entre elles. Je ne comprends pas comment prouver une combinaison d'entre eux, comme dans le problème. Quelqu'un pourrait-il m'expliquer cela?Comment prouver une combinaison de notations asymptotiques?
Θ (n) + O (n^3) = O (n^3)
modifier: faute de frappe, à l'origine avait dit pas égal
En fait, je pense que Θ (n) + O (n^3) = O (n^3).
Si vous avez une fonction f avec des constantes k1 et k2 telles que k1 * n < = f (n) < = 2 m end * n asymptotiquement (qui est le Θ), et vous avez une fonction g avec k3 constante telle que g (n) < = k3 * n^3 asymptotiquement (c'est le big-O de gauche), alors il y a une constante k4 telle que f (n) + g (n) < = k4 * n^3 asymptotiquement (le bon gros- O). Prenez simplement k4 = k2 + k3 et limitez-vous à n> = 1, car si n> = 1 alors k2 * n + k3 * n^3 < = k2 * n^3 + k3 * n^3 = (k2 + k3) * n^3 = k4 * n^3.
Pour afficher une inégalité comme celui que vous demandez est plus simple: vous avez juste besoin d'exposer spécifique f et g qui satify les limites pour le côté gauche, mais où f (n) + g (n) ne satisfait pas les limites pour le côté droit.
Ce résultat semble faux. D'où avez-vous eu cela? – templatetypedef
Oups. Je pense que je l'ai tapé mal. Merci d'avoir fait remarquer cela. – helpmeeeee