„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
| 3. sor: | 3. sor: | ||
==2013.04.03. ZH megoldásai== | ==2013.04.03. ZH megoldásai== | ||
===1. Feladat=== | ===1. Feladat=== | ||
Mi az a legkisebb ''r'' racionális szám, melyre teljesül, hogy <math>\sqrt{1} + \sqrt{2} + \sqrt{3} + ...+\sqrt{n} = O(n^{r}) ?</math> | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*Először megpróbáljuk felülről becsülni: | |||
**Felülről becsüljük a sorozatot, ha az elemeket rendre <math>\sqrt{n}</math>-nek tekintjük, vagyis:<br><br> | |||
**<math>\sqrt{n} + \sqrt{n} + \sqrt{n} + ...+\sqrt{n}=n\cdot\sqrt{n}=n^{1.5}=O(n^{1.5}) \Rightarrow r=1.5</math><br><br> | |||
*Most pedig megpróbáljuk alulról becsülni: <br><br> | |||
**Alulról becsüljük a sorozatot: <br><br> | |||
**<math> \frac{n}{2 } \cdot \sqrt{1}+\frac{n}{2} \cdot \sqrt{n} \leq \sqrt{1} + \sqrt{2} + \sqrt{3} \dots \sqrt{n} </math> <br><br> | |||
**<math> \frac{n}{2 } \cdot \sqrt{1}+\frac{n}{2} \cdot \sqrt{n} = O(n^{1.5}) \Rightarrow r=1.5. </math> <br><br> | |||
*A kettőt együttvéve látszik, hogy <math> r = 1.5 .</math> | |||
}} | }} | ||