Aider avec le Grand Oméga de la Preuve?
J'ai de la difficulté à résoudre un preuve. Où t(n) <= cn^1.6, c étant une constante. En général, les Gros Omega est à l'opposé de Big O en ce qu'il est le meilleur des cas scenerio et regarde pour la limite inférieure. Alors il existe un c et et n0 tel que n >= n0. Mais je suis pas sûr de la procédure à appliquer à la preuve et la manière de manipuler les constantes de l'équation pour trouver c et n0 et pour prouver que t(n) est Omega(n^1.6).
t(n) = (n-3logn)^1.6 + 5n^1.5 + 7 est Omega(n^1.6)
Quelqu'un pourrait-il offrir des conseils sur la façon de faire ce type de problème? Merci à l'avance!
Aussi si je n'obtiens aucune critique n'a été reçu du commentaire en dessous de moi, ce n'est pas un problème mais un exemple d'un ensemble d'exercices, de sorte qu'il est plus facile pour quelqu'un pour expliquer le concept général derrière ce type de problème.
OriginalL'auteur deedex11 | 2011-02-24
Vous devez vous connecter pour publier un commentaire.
Définition de la Grand-Omega: f(n)=Omega(g(n)) ssi les constantes C et K existe tel que pour tout n > K, f(n) > C * g(n)
En d'autres termes, vous devez être en mesure de dire quelque chose comme ceci: "je choisir C = 5, et maintenant, pour tous les n > 1000, f(n) > 5 * g(n), donc il."
Passons à votre problème maintenant.
Diviser par n^1.6
Examinons donc ces trois termes un par un (en plus de la preuve formelle serait nécessaire, bien sûr, mais ce sont de simple).
Nous voyons donc que, pour tout n > 2, C < 1 + 5 + 1 = 7
Maintenant, vous obtenez de dire "je choisir C=7, et pour tout n > 2, C*n^1.6 < ..."
OriginalL'auteur iluxa