#2 18. 03. 2010 22:19 — Editoval Kondr (21. 03. 2010 12:17)
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: algoritmy a zlozitost - dokaz
Ten symbol uprostřed neodpovídá běžným konvencím: má vyjadřovat, že funkce nerostou stejně rychle? Pokud jo, tak urči limitu podílu levé a pravé strany a pokud [EDIT] nenulové reálné číslo[/EDIT], tvrzení je dokázáno.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#3 21. 03. 2010 09:04 — Editoval hbm (21. 03. 2010 09:10)
Re: algoritmy a zlozitost - dokaz
Zdravim, mno ja som takisto nevedel co ma symbol vyjadrovat, ale uz sa mi dostalo odpovede od kompetentnych, tz
>< je theta-notacia, f(n) = theta(g(n)) takze mam dokazat, ze c1g(n) ≤ f(n) ≤ c2g(n) , pre c1,c2 > 0 neplati.
Podla toho, ako to ja chapem ste mal v podstate pravdu:
- to ukazuje, ze c1g(n) ≤ f(n) pre dost velke n
- a tu trz neviem, kedze tato limita vysla vatsia ako 1, potom to dokazuje, ze neplati f(n) ≤ c2g(n) ?
resp. ta 1 je len blbost v mojej hlave ale ajtak to dokazuje, ze toneplati, kedze lim. vysla nekonecno ?
Offline
#4 21. 03. 2010 12:20
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: algoritmy a zlozitost - dokaz
↑ hbm: Ještě jsem editoval svůj předchozí příspěvek, není nutné, aby ta limita vyšla 1. Vztah c1g(n) ≤ f(n) ≤ c2g(n) je ekvivalentní s c1 ≤ f(n)/g(n) ≤ c2. Protože taková c1,c2 nenajdeš (podle toho co je f a co je g vyjde buď jedno z nich 0 nebo druhé nekonečno, což nejsou reálné nenulové konstanty), zadané tvrzení platí.
BRKOS - matematický korespondenční seminář pro střední školy
Offline