„Algoritmuselmélet 2010.11.19. PZH megoldásai” változatai közötti eltérés
| (Egy közbenső módosítás, amit egy másik szerkesztő végzett, nincs mutatva) | |||
| 2. sor: | 2. sor: | ||
== 2010.11.19 - PZH megoldásai== | == 2010.11.19 - PZH megoldásai== | ||
===1. Feladat=== | ===1. Feladat (Van megoldás)=== | ||
Az alábbi függvényeket rendezze olyan sorozatba, hogy ha <math> f_i </math> után közvetlenül <math> f_j </math> következik a sorban, akkor <math> f_i(n) = O(f_j(n)) </math> teljesüljün! | Az alábbi függvényeket rendezze olyan sorozatba, hogy ha <math> f_i </math> után közvetlenül <math> f_j </math> következik a sorban, akkor <math> f_i(n) = O(f_j(n)) </math> teljesüljün! | ||
| 17. sor: | 17. sor: | ||
*<math> f_3(n)=4^{100+logn} = 4^{100} \cdot 4^{logn} = 4^{100} \cdot (2^2)^{logn} = 4^{100} \cdot (2^{logn})^2 = 4^{100} \cdot n^2</math><br><br> | *<math> f_3(n)=4^{100+logn} = 4^{100} \cdot 4^{logn} = 4^{100} \cdot (2^2)^{logn} = 4^{100} \cdot (2^{logn})^2 = 4^{100} \cdot n^2</math><br><br> | ||
*Első lépésben belátjuk, hogy <math> | *Első lépésben belátjuk, hogy <math> f_1(n)=O(f_3(n)). </math><br><br> | ||
**<math> 2010n \cdot log_3n \leq c \cdot 4^{100} \cdot n^2 </math><br><br> | **<math> 2010n \cdot log_3n \leq c \cdot 4^{100} \cdot n^2 </math><br><br> | ||
**<math> 2010 \cdot log_3n \leq c \cdot 4^{100} \cdot n </math><br><br> | **<math> 2010 \cdot log_3n \leq c \cdot 4^{100} \cdot n </math><br><br> | ||