Matematické Fórum

terrmith · 02. 03. 2010 13:18

Ahoj,
už nějakou dobu se snažím indukcí dokázat, že

log{2}(n) <= c*sqrt(n)
n > 1, c > 0

Bázový krok je celkem jasný podle grafu. Možná důkaz ulehčí správná volba c, ale nijak jsem toho využít nedokázal.
V indukčním kroku jsem se nejblíž asi přes tento vzorec, ale ani to jsem nakonec nedokázal dotáhnout do konce:
x = a^(log{a}x)
tedy
sqrt(x) = 2^( log{2}(sqrt(x)) )

Poradil by mi někdo?

musixx · 02. 03. 2010 15:26 — Editoval musixx (02. 03. 2010 15:53)

Chtělo by to nějaké kvatifikátory... Chceš dokázat, že $\forall n\in{\mathbb N}\ \exists c\in{\mathbb R}:\ \log_2(n)\leq c\sqrt n$ ? Nebo $\exists c\in{\mathbb R}\ \forall n\in{\mathbb N}:\ \log_2(n)\leq c\sqrt n$ ? Nebo ještě nějak jinak? Nebo chceš najít minimální $c$ v závislosti / nezávisle na $n$ ?

EDIT: Samozřejmě je tu otázka, nakolik je využitelná informace o n-1 (resp. klidně i o všech "předchozích") pro usuzování o n. A tedy jestli matematická indukce je tady ten správný nástroj.

terrmith · 02. 03. 2010 16:07

Potřebuji dokázat to, že logaritmus roste pomaleji než odmocnina. Asi bych to formuloval takhle:
Dokažte, že pro všechna n z N-{0..x} platí, že log{2}(n)<= c*sqrt(n), kde x je poslední bod, pro který tvrzení neplatí. c je konstanta, která rychlost růstu funkce už neovlivní, došlo by pouze k posunutí bodů, kde se funkce kříží.
Například, pro c=1, by x bylo 15 a v bázový krok by vypadal takto:
log{2}(16) <= 1*sqrt(16)
4 <= 1*4

musixx · 03. 03. 2010 08:53 — Editoval musixx (03. 03. 2010 11:36)

Není tak těžké najít extrém funkce $f(x)=\log_2(x)-c\sqrt x$ a z toho spočítat, že když zvolíme $c=\frac2{e\cdot\ln2}\dot=1.0615$ , tak na celém definičním oboru je $\log_2(x)\leq c\cdot\sqrt x$ , přičemž navíc toto $c$ je nejmenší s touto vlastností. Stačíš mě sledovat?

EDIT: A šel jsem na to prostředky matematické analýzy, nikoli matematickou indukcí.

EDIT2: BTW: Neptáš se náhodou proto, že máš dokázat, že algoritmy složitosti $O(\log n)$ jsou vždy (limitně) lepší než algoritmy složitosti $O(n^k)$ ?

EDIT3: Jen pro zajímavost -- obecněji pro $a>1$ , $k>0$ , $\log_a(x)$ a $c\cdot x^k$ máme, že $c=\frac1{e\cdot k\cdot\ln a}$ je ta "naše" konstanta.

terrmith · 03. 03. 2010 15:08

Heh, zajímavej způsob. Já bych řekl, že ani není třeba počítat tu konstantu. Stačilo by ukázat, že funkce rozdílu pouze klesá od určitého bodu.
I tak by mi ale zajímalo jak by se na to šlo přímo tou indukcí. To že nedokážu dokázat takhle jednoduchý funkce znamená, že neznám nějakej podstatnej trik :)

ad edit2: No, je to příklad na složitost, ale jde jen o to jestli je log2(n) v O(n^0.5).

musixx · 03. 03. 2010 15:50 — Editoval musixx (03. 03. 2010 16:03)

terrmith napsal(a):
... jak by se na to šlo přímo tou indukcí. To že nedokážu dokázat takhle jednoduchý funkce znamená, že neznám nějakej podstatnej trik :)

Příliš odvážný úsudek, řekl bych. Jak už jsem jednou psal -- indukce tady není ten pravý aparát. Z $\sqrt{n-1}-\log_2(n-1)$ (resp. z $\sqrt{n-n_0}-\log_2(n-n_0)$ ) se nedá jen tak snadno usoudit nic o $\sqrt n-\log_2(n)$ .

terrmith napsal(a):
No, je to příklad na složitost, ale jde jen o to jestli je log2(n) v O(n^0.5).

V daleko obecnější podobě ti odpovídá můj edit3 výše (napsal jsem jej právě proto, že jsem tušil, že budeme mířit ke složitostním třídám). Jakýkoli logaritmus se základem větším jak jedna je z pohledu teoretické složitosti lepší než jakákoli mocnina s kladným exponentem (i když v praxi to může být trošku jinak, jak jistě víš). EDIT: A protože jsem výše vždy našel nejmenší potřebné c, tak by se dal najít i minimální počet operací, od kterého je onen logaritmus lepší.

Pavel · 03. 03. 2010 17:19

↑ terrmith:

Vyjdu z nerovnosti $2\sqrt{n+1}<Kn\ln 2$ , u níž není problém ukázat, že pro fixní $K$ platí pro dostatečně velká $n$ . Přirozených čísel $n$ , pro která tato nerovnost neplatí, je konečně mnoho a pro ně stačí ověřit původní nerovnost přímým výpočtem. Zabývejme se tedy těmi přirozenými čísly $n$ , pro které platí

$2\sqrt{n+1}<Kn\ln 2\qquad (1)$

a položme indukční předpoklad

$\log_2{n}<K\sqrt n\qquad (2)$

Nerovnost (1) lze upravti na tvar

$\frac{1}{n\ln 2}<\frac{K}{2\sqrt{n+1}}\qquad (3)$ .

Nyní použiju Lagrangeovu větu o střední hodnotě na funkci $\log_2 x$

$\frac{\log_2(n+1)-\log_2 n}{n+1-1}=(\log_2\xi)'=\frac 1{\xi\ln2},\qquad \xi\in(n,n+1)\nl \log_2(n+1)-\log_2 n<\frac 1{n\ln2}\qquad\Rightarrow\qquad \log_2(n+1)<\log_2n+\frac 1{n\ln2}\qquad(4)$

Znovu použiju Lagrangeovu větu o střední hodnotě na funkci $K\sqrt x$

$\frac{K\sqrt{n+1}-K\sqrt x}{n+1-1}=(K\sqrt\xi)'=\frac K{2\sqrt\xi},\qquad \xi\in(n,n+1)\nl K\sqrt{n+1}-K\sqrt n>\frac K{2\sqrt{n+1}}\qquad\Rightarrow\qquad K\sqrt{n+1}>K\sqrt n+\frac K{2\sqrt{n+1}}\qquad(5)$

Použijme postupně nerovnost (4), indukční předpoklad (2), nerovnost (3) a nakonec nerovnost (5):

$\log_2(n+1)<\log_2n+\frac 1{n\ln2}<K\sqrt n+\frac 1{n\ln2}<K\sqrt n+\frac{K}{2\sqrt{n+1}}<K\sqrt{n+1}.$

Tím je důkaz indukcí hotov.