Matematické Fórum

VojtechSejkora

mám časovku

$O(10^{cifer}-10^{cifer-1})$
to že je hodně nepříjemná neřešte, mě jde jen o to jestli se tam ten 2. člen nechává nebo ne

a pak když budu mít časovku
$O(10^{\frac{cifer}{2}}$ tak jestli to dělení dvěmi tam je nebo taky ne

čímž by pak tyto dva algoritmy měli stejnou složitost

pizet · 31. 03. 2011 16:56 — Editoval pizet (01. 04. 2011 21:11)

No ak dajme tomu, že $f(n) = 10^n-10^{n-1}$ a $g(n) = 10^{\frac{n}{2}}$ , tak (ak rátam správne), tak $g = O(f)$ ale $f \neq O(g)$ . Mohol som sa ale seknúť.

VojtechSejkora · 01. 04. 2011 20:44

↑ pizet:
tak z toho jsem teda mnohem moudřejší... ne vážně, nemohl by jsi to ukázat nějak polopatě? mimochodem $f(n) = 10^n-10^{n-1}$ je dle zadání spíš nikoliv s +,ale s mínusem

mě by stačilo, kdyby jsi mi řekl jestli se to zapíše jako $O(10^n)$ a nebo se to tak zapsat nemůže

a pak jestli $O(10^\frac{n}{2})$ je to stejné jako $O(10^n)$

pizet · 01. 04. 2011 21:18

Sorry, ja som to rátal s mínusom, len som to zle napísal.

No z toho čo som ja napísal (ak je to správne) vyplýva, že odpoveď na tvoju druhú otázku je nie, teda algoritmy by nemali mať rovnakú zložitosť.

Odporúčam si prečítať toto http://www.cs.berkeley.edu/~vazirani/al … /chap0.pdf - tam sú tieto veci celkom pekne povysvetlované ale ja preto ešte nemám úplné pochopenie, preto sa radšej neriaď mojimi radami - čakal som, že niekto iný tiež odpíše.

Lumikodlak · 01. 04. 2011 23:37

Da se take najit neco na wikipedii. Jestli jsem to spravne pochopil, tak zjednodusene - kdyz jsou dve slozitosti, a nasobenim konstantou (nenulovou :-) ) se da zaridit, aby jedna slozitost byla vetsi nez druha pro kazde n, tak jsou ekvivalentni. Napriklad $O(n^2+5n)$ je vzhledem ke slozitosti to same jako $O(5n^2-3n)$ (kdyz se prvni vynasobi 5, tak bude vetsi nez druha pro kazde n, kdyz se druha vynasobi treba 4, tak bude vzdy vetsi nez druha, obe jsou take stejne jako $O(n^2)$ ).
Ve tvem pripade ta prvni je $10^n-10^{n-1} = 0.9\cdot10^n$ , takze to bude $O(10^n)$ .
To ale nebude stejne jako $O(10^{\frac{n}{2}})$ , protoze neni konstanta, kterou bys mohl vynasobit $10^{\frac{n}{2}}$ tak, ze by to bylo vetsi nez $10^n$ pro vsechna n.
To je tak vse, co me k tomu napada :-)