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.
Algorytmy - złożoność obliczeniowa
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
ViolinFinnigan
- Dopiero zaczynam
- Posty: 28
- Rejestracja: 26 lis 2020, 13:38
- Podziękowania: 14 razy
- Płeć:
-
Icanseepeace
- Stały bywalec
- Posty: 443
- Rejestracja: 03 kwie 2021, 21:36
- Podziękowania: 6 razy
- Otrzymane podziękowania: 254 razy
- Płeć:
Re: Algorytmy - złożoność obliczeniowa
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)) \)
\( \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)) \)