Preuves d'algorithme

Question

Dans ce cas, f (n), g (n) et h (n) sont des fonctions asymptotiquement positives, ce qui signifie qu'il existe un N tel que f (n)/g (n)/h (n)> 0, pour tout n> = N. Étant donné que:

f(n) = Θ(g(n)) 
g(n) = Θ(h(n)) 

J'ai besoin de prouver que

f(n=Θ(h(n))). 

Il est suggéré d'utiliser la définition formelle de Θ, qui stipule que si f (n) = Θ (g (n)) signifie qu'il existe des constantes positives c1, c2 et k, telles que 0 ≤ c1g (n) ≤ f (n) ≤ c2g (n) pour tout n ≥ k. Les valeurs de c1, c2 et k doivent être fixées pour la fonction f et ne doivent pas dépendre de n. J'ai trouvé des exemples similaires à cela, mais je ne suis toujours pas sûr de la façon de résoudre ce problème. Est-ce que quelqu'un peut-il me montrer la bonne direction?

EDIT: Ma proposition actuelle est d'essayer d'utiliser la propriété transitive, qui indique si a = b et b = c alors a = c. Je ne suis pas sûr que ce soit exactement correct mais c'est ma meilleure estimation pour l'instant. La syntaxe de la f (n = Θ (h (n))) me confond le plus. Je ne suis pas complètement sûr de comment l'interpréter.

Answer 1

En supposant que f (n = Θ (h (n))) est le même que f (n) = O (h (n)), puis en utilisant la définition de grande 0, ce qui indique:

f = O(g) iff exist c, n0 > 0 such that forall n >= n0 then 0 <= f(n) <= cg(n) 
g = O(h) iff exist k, n1 > 0 such that forall n >= n1 then 0 <= g(n) <= kh(n) 

alors je peux diviser la dernière inégalité et diviser par tous les membres

c: 0 <= f(n)/c <= g(n) 

et substitut g (n) avec

0 <= f(n)/c <= kh(n) 

puis multiplier par tous c, nous donnant

0 <= f(n) <= kch(n) 

qui est équivalent à f = O (h). Donc

f = O(h) iff exist j, n2 > 0 such that forall n >= n2 then 0 <= f(n) <= jh(n)