Algorytmy - złożoność obliczeniowa

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
ViolinFinnigan
Dopiero zaczynam
Dopiero zaczynam
Posty: 24
Rejestracja: 26 lis 2020, 13:38
Podziękowania: 13 razy
Płeć:

Algorytmy - złożoność obliczeniowa

Post autor: ViolinFinnigan »

Wykaż, że jeśli f(n)=O(g(n)) oraz h(n)=O(q(n)) to f(n)*h(n)=O(g(n)*q(n))

Mam takie o to zadanko i zastanawiam się, jak je ugryźć. Myślałam, by spróbować coś wzorami skróconego mnożenia i tymi niewieloma właściwościami notacji O, ale coś mi nie idzie.
Icanseepeace
Stały bywalec
Stały bywalec
Posty: 434
Rejestracja: 03 kwie 2021, 21:36
Podziękowania: 6 razy
Otrzymane podziękowania: 250 razy
Płeć:

Re: Algorytmy - złożoność obliczeniowa

Post autor: Icanseepeace »

Skoro \( f(n) \in O(g(n)) \) to istnieje \( n_1 \in N \) oraz jakaś stała \( C_1 > 0\) takie, że:
\( \forall_{n \geq n_1} f(n) \leq C_1 g(n) \)
analogicznie skoro \( h(n) \in O(q(n)) \) to znajdę \( n_2 \in N \) oraz stałą \( C_2 > 0 \) takie, że
\( \forall_{n \geq n_2} f(n) \leq C_2 g(n) \)
Niech teraz \( n_0 = \max \{ n_1 , n_2 \} \). Wtedy dla wszystkich \( n \geq n_0 \) mamy:
\( f(n) \cdot h(n) \leq C_1 \cdot C_2 \cdot g(n) \cdot q(n) = C \cdot g(n)q(n) \)
A to oznacza, że \( f(n) \cdot h(n) \in O(g(n)q(n)) \)
ODPOWIEDZ