Chceš tím říct, že "tvoje" definice je v praxi nepoužitelná, zvlášť pokud je délka vstupu konstantní? Pak souhlasím. Protože v praxi algoritmy pracují s daty ve fixním formátu.
Chci tim říct, že bavit se o ASYMPTOTICKÉ složitosti, tedy vyšetřovat jaké je chování algoritmu při přibližování nějaké veličiny (ať již jde o délku vstupu nebo o cokoli jiného) limitně k NEKONEČNU, je u fixního vstupu blbost, protože fixní vstup se nikdy k nekonečnu blížit nebude, anžto má horní hranici.
Jako bys tvrdil, že třídění má složitost lineární a dokazoval to tím, že když uděláš algoritmus, kterej bude mít na vstupu pevných sto chlívků pro čísla, z nichž některé budou prázdné, ale ty chlívky budou mít libovolnou velikost, tak algoritmus, co ten vstup seřadí bude mít lineární složitost.
Algoritmus, který by uměl pracovat s libovolně velkým n, je jiný algoritmus (složitější a pomalejší - alespoň dokud nebudou existovat stroje, které umějí zpracovávat libovolně velká data).
1) Nový kolečko? NP třídy jsou definovaný pomocí turingova stroje. Ne na reálnym HW.
2) Zpracovámí dlouhých čísel je i na současném HW vcelku jednoduchá úloha s lineární složitostí (potřebuji jen sčítání a porovnávání). Takže nevím, proč by mělo jít o "pomalejší" algoritmus. Jelikož je sublineární algoritmus je nesmysl (BÚNO vždycky alespoň vstup přečtu), tak předělání algoritmu z fixed width na variable length neudělá s asymptotickou složitostí vůbec nic.
3) Asymptotická složitost z definice prostě nemůže používat pevný zápis vstupu, protože ten je omezen (viz předchozí odstavec).
4) Ty se fakt chceš bavit o složitosti na reálném hardware? A budeš do toho počítat velikosti různejch cache a pamětí? Takže na spoustě míst najednou nastane skok, jak nebude stačit na ta a ta data L1/L2/L3 cache či paměť - jak to do výpočtu zahrneš?
A můžu na tom stroji akcelerovat pomocí GPGPU? A jak do výpočtu zahrneš TLB, asociativitu cache, branch prediction....? A jak chceš řešit asymptotickou složitost, když od určitý velikosti se Ti to nevejde ani na harddisk? A....
Promiň, ale to je prostě blbina, složitost se vždy počítá na nějakém abstraktním stroji a pokud je důležité kódování vstupu, tak na TS.
Tohle je ale jiná indukce:
Pro krok n je vyžadováno, aby byly vyřešeny všechny kroky od 1 do n-1. Zdůrazňuji termíny "všechny" a "1". Krok pro nulu nemá žádný význam.
Ano, a kdo to stanovil, že se musí začít od jedničky? Báťuška Stalin a tak je to pravda? Nebo to učili v mateřský škole? A oni jsou nějaký dvě matematický indukce? Omlouvám se za sarkasmus, ale fakt by to chtělo, aby sis o věcech, o kterejch píšeš něco zjistil, nebo to alespoň netvrdil tak jistojistě.
Jak např. dokážeš, že kůň na šachovnici n*n doskáče všude, když to platí jen na šachovnici 4x4 a větší? To jako tady indukci použít nesmím, protože se MUSÍ začít od jedničky?
Pro matematickou indukci je nutné dokázat že:
1) P(n_0), n_0 náleží do Z
2) Pro každé n ze Z: n >= n_0 platí P(n) => P(n+1)
A tím dokážeš, že tvrzení P platí pro každé n větší rovné n_0
http://math.feld.cvut.cz/habala/teaching/dma/dmknih03.pdfsvěte div, se, pokud to chci dokázat pro všechna celá čísla, tak dokonce budu dokazovat i
P(n+1) => P(n). Jaká svatokrádež! :-) :-) :-)
PS: (pro složitější důkazy se druhá implikace nahrazuje)
2) Pro každé n ze Z: n > n_0 platí: P(n_0) & P(n_0 + 1) & ... & P(n - 1) => P(n)
159 Odpovědí
54081 Zhlédnutí