Definice časové složitosti

[slowthinker]

Panove, mohl bych vas o neco poprosit? Zajimalo by me vase vzdelani (kde, co a rocnik/dosazeny titul) . Od vsech...

Já mám základní školu. Titul mi tam bohužel nedali.
A tvoje vzdělání? Ptám se proto, že jsem slyšel, že dneska má titul každý blbec, ale protože jsem sám na vysoké škole nestudoval, nemohl jsem si to na místě ověřit. Možná, že bys mi to mohl osvětlit?

_{(výše uvedeným odstavcem jsem chtěl říct: proč tě to vůbec zajímá?)}

[Reklama]

[host]

a nebyla by z praktickeho hlediska lepsi amortizovaná složitost?

[j.]

Mateji:
Jaka je to O slozistost (bod c)? O(1)? Jses si jist, ze chces aby F melo mensi slozitost nez B? (priklad prave s jednickovou a dvojkovou notaci zapisu vstupu a vystupu a tridenim). A je nlog(n), B je linearni (dokonce pravdepodobne sublinearni), F je linearni, G je exponencialni.

v jakých formátech mohu příjmat vstup, abych pořád byl stejně rychle schopen vyřešit daný problém* a naopak jaké algoritmy mohu použít pro řešení daného problému

A prave diky existenci polynomialni redukce mezi vsema NP-uplnyma problemama ti vsechno spadne do jedne tridy... Tu podminku by bylo potreba nastavit daleko jemneji, ale neumim si predstavit jak. Chces davat dokupy problemy z ruznych slozitostnich trid, a v principu nevidim rozdil mezi "konverzii" vstupu/vystupu, kterou jeste intuitivne povazujes za rozumnou a vsema dalsima.

[Logik]

host: Než co?
j:
O složitostí myslím prostě takovou tu s omega se zanedbáním konstant. :-)

Jses si jist, ze chces aby F melo mensi slozitost nez B

U F myslím ano, u G by ji to chtělo definovat v závisloti na velikosti nikoli vstupu G, ale vstupu algoritmu....

F je linearni, G je exponencialni.

Právě kvůli tomudle.

Ty podmínky mají v podstatě vyjádřit. B řeší A do té doby, dokud pre/postproces řešení B není náročnější než samotné řešení B.

B je linearni (dokonce pravdepodobne sublinearni),

IMHO není lineární. Lineární je vzhledem k růstu čísla, ale nikoli vzhledem k růstu počtu čísel. Takže je furt taky nlog(n). Nebo se pletu?

A prave diky existenci polynomialni redukce mezi vsema NP-uplnyma problemama ti vsechno spadne do jedne tridy...

Jen všechny NP úplné. A to mi zas tak nevadí, svým způsobem to je vlastně jeden a ten samý problém, jen s jinou "omáčkou".

Chces davat dokupy problemy z ruznych slozitostnich trid,

Nechci. Problém batohu za danejch podmínek na problém setřídění nepřevedeš. A problém setřídění na problém batohu asi nějak půjde, ale zas daný problém pak zařadím do "minimální" možné třídy, tzn. vyberu ten podobný algoritmus, který má nejmenší složitost.
Jinými slovy, třídění přímým výběrem je podobné heapsortu, ale obecně problém třídění (jemuž jsou podobné oba tyto algoritmy) zařadím do nlogn, protože jsem schopen najít podobný algoritmus, který to v nlog(n) řeší.

a v principu nevidim rozdil mezi "konverzii" vstupu/vystupu, kterou jeste intuitivne povazujes za rozumnou a vsema dalsima.

Právě proto tam mam podmínku, že konverze musí bejt jednodušší než algoritmus samotný.

[j.]

Uz se ztracim, zkus si to znovu setridit a poradne vyformalizovat...

B je linearni (dokonce pravdepodobne sublinearni),

Predpokladam, ze B dostava na vstupu cisla v "jednickove" soustave oddelene mezerou. Prvni co mne napada je, ze mozny algoritmus, ktery prevede stup delky n na nejakou n-arni (n>=2) (linearni slozitost vzhledem ke vstupu), cim dostane delku vstupu k=log(n), setridi (O(k*log(k))=O(log(n)*log(log(n))) a prepise zpatky na "jednickovou" (zase linearni k puvodnimu vstupu) - celkove linearni slozitost vzhledem k delce vstupu (porad se bavime o formalni definici, teda asymptotycka slozitost turingova stroje vzhledem k delce vstupni pasky.

[Reklama]

[Logik]

No ale přeci když tam budou samé jedničky, tak je prostě setřídíš v čase nlog(n), ne?

IMHO máš chybu v tom, že převedení na binární soustavu nezkrátí logaritmicky vstup. Vstup se zkrátí jen na délku cca
log(n/m)*m
Přesně to bude pokud budou čísla stejně dlouhá, což vzhledem k tomu, že si pro dané n mohu vybrat "nejhorší vstup" mohu zaručit (nebo asi spíš skoro zaručit až na nějakou nepodstatnou konstantu)
log(n/m)*m =  log(n)*m - log(m)*m < 1/2 log(n)*m = omega(log(n)*m)
pokud tedy m * log(n) > n,

Jelikož vstupy, kde
m = C * n/log(n)
existují, tak existjí vstupy délky n, pro které bude pořád složitost n log (n).
Nebo dělám někde chybu?

[j.]

Moc to komplikujes, taky jsi mohl rict ze mam na vstupu (n+1)/2 jednicek oddelenych (n-1)/2 mezerama (1 1 1 1 ... 1). Pak se vstup nezkrati vubec.

Nevybral jsem dobry priklad, tak si misto unarni soustavy predstav vstup typu k1_s1_k2_s2...km, kde k1-km jsou cisla v dvoukove soustave o celkove delce j, s1-s(m-1) jsou sum vzdy delky (2^j)/m. Setridit to je asymptotycky stejne slozite jako vyparsovat z toho cisla k1-km (tech par operaci pouzitych pri samotnem trideni se strati pod samotnym parsingem, ktery je na turingovem stroji s jednou paskou polynomialni ke vstupu - parsing vzdy O(n^a)=O(2^a*j), kde a je stupen polynomu, trideni O(j*log(j))=O(log(n)*log(log(n))), dokopy O(n^a)).

Ale to uz tezce odbocujeme od hlavni temy. Zkus znovu zformalizovat tu relaci podobnosti problemu.