@Matyáš Novák
ano, můj nick je přesný. Lepší myslet pomalu než blbě jako někteří, které nechci jmenovat :p
Po mnohahodinovém úsilí mi došlo, co mi chceš sdělit. Veškeré naše nepochopení se zřejmě točí kolem tvé následující věty:
Složitost algoritmu se prostě měří dle závislosti rychlosti (popř. spotřebované paměti) na velikosti (počtu bitů) vstupu.
(místo "rychlosti" má být zřejmě "doby běhu")
To je podle mne špatný způsob měření. Vysvětlím na dvou příkladech:
_______________________________________________________
Příklad 1
Porovnejme následující algoritmy:
Algoritmus A)
Na vstup dostane přirozené číslo n, spočte jeho faktoriál
Algoritmus B)
Na vstup dostane n čísel, spočte jejich součin
Algoritmus C)
Na vstup dostane čísla 1, 2 ,3, 4 ...n , ověří vzestupnost posloupnosti, pak spočte jejich součin stejným postupem jako A)
Všechny tři algoritmy mají stejný charakter: jedná se o jeden for cyklus od 1 do n, uvnitř cyklu se pouze násobí (A a C jsou dokonce v podstatě totožné). Tvrdím proto, že časová náročnost všech algoritmů je stejná. A také tvrdím, že způsob určování časové náročnosti, který toto popírá, nemá z praktického hlediska žádný význam (dále budu zkráceně říkat "je špatný")
Tvůj způsob určování časové náročnosti (tj. délka běhu programu striktně vztažená k bitové délce vstupu) je tedy špatný.
Je to způsobeno tím, že vstupy algoritmů A), B) a C) mají jistou charakteristiku (zcela nezávislou na bitové délce vstupu), a tou je "n". Toto "n" (a NIKOLI bitová dělka vstupu) je právě tou charakteristikou, která určuje smrštěni-natažení běhu programu a ovlivňuje dobu jeho běhu.
_____________________________________________________________
Příklad 2
Uvažujme algoritmus, který na vstupu dostane dvě čísla v daném formátu (dejme tomu word), a na výstupu odevzdá jejich součet. (algoritmus nedokáže přijímat a sčítat libovolně velká čísla)
Jak určíš časovou náročnost dle tvé definice? Ty říkáš, že je to exponenciální náročnost (odpověď #33, 2. odstavec), což je samo o sobě dosti překvapivý závěr. Jenomže zapomínáš, že délka vstupu tohoto algoritmu je ve skutečnosti neměnná, takže nelze uvažovat ani žádnou asymptotickou funkci, ani určovat časovou náročnost.