Comment prouver les relations big-o

Question

Hé, le titre est probablement un peu éteint, alors s'il vous plaît corriger si vous savez comment le mettre mieux.

En tant que devoir à la maison m'a donné plusieurs missions le long de ce qui suit:

Soit f (n) et g (n) fonctions asymptotiquement positives. Prouver ou réfuter chacune des conjectures suivantes. Maintenant, ma vraie question est - comment allez-vous prouver cela de façon formelle? Je sais que ce qui précède serait facile car je pourrais facilement fournir un contre-exemple pour le réfuter, mais pour le bien de l'argument disons que nous voulons le faire sans contre-exemples, comme bien sûr cela continue avec d'autres exemples où cela ne fonctionnera pas.

Je suis un peu coincé, j'ai les inégalités suivantes rédigé (avec < = étant inférieur ou égal à)

f(n) <= c1 * g(n) 
g(n) <= c2 * f(n) 

Mais je ne suis pas certain de la façon dont je combiner ces 2 inéquations en un seul (in) équation et réfuter. Je suis tout à fait certain que c'est quelque chose de très facile que j'ai simplement oublié et que je suis plutôt stupide en ce moment - mais n'importe quel pointeur/exemple concret de la façon de faire cela serait génial, pour que je puisse travailler reste de ces questions par moi-même. Pourquoi voulez-vous le réfuter sans utiliser un contre-exemple?

Answer 1

C'est le moyen le plus direct de réfuter une réclamation.

Si vous deviez le prouver à la place, bien sûr, vous ne seriez pas en mesure d'utiliser un contre-exemple. Dans ce cas, la contrapositive peut très bien fonctionner - supposer que la revendication est fausse, puis montrer comment cela conduit à une incohérence logique.

Dans ce cas, vous commencez par f(n) <= c1 * g(n) étant vrai, puisque c'est ce que l'on entend par f(n) = O(g(n)). Maintenant, vous voulez supposer que g(n) <= c2 * f(n) est vrai pour tous f et g (cette dernière partie est très importante, car vous pouvez certainement choisir f et g de telle sorte que c'est vrai), et montrer pourquoi cela ne peut pas fonctionner. Mon indice pour vous: choisissez un f et un g de sorte qu'il ne peut pas fonctionner, et montrer qu'il ne peut pas travailler par votre choix de c1 et c2.

Answer 2

Quelques conseils:
Ne pas oublier que f(n) = O(g(n)) est un set notation et vous pouvez le convertir en une forme mathématique des inégalités.

opérations simples que vous pouvez faire avec le O -notation:

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), si c est constante
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))

(L'art de la programmation informatique, vol 1 - Le O -Notation)