Pamatova zlozitost – Offtopic – Fórum – Programujte.com

Zdravim,mohol by mi niekto prosim vas trochu vysvetlit pamatovu zlozitost? Aspon ako sa urcuje,nejake zaklady ,ci sa to odvodzuje od casovej ,alebo je taka ista ako casova .Dakujem,moc by mi to pomohlo :)

Pobavil :) Zkus se nad temi pojmy zamyslet. Pametova je od slova pamet. Casova od slova cas. Kdyz na disk narves 4M, tak to neni totez jako 50 mikro sekund.
Naroky na pamet, pokud je chces nejak pocitat, tak zavisi na algoritmu a delce vstupnich dat.
Kdyz das serazovat algoritmem 4 miliony cisel, tak to seradi za tech 50 mikro sekund, rekneme. Pak to zavisi tedy na tom, jak ten algoritmus pracuje, kolik dalsi pameti bude potrebovat.

Jiny priklad. Potrebujes vykopat kanalek pro polozeni kabelu. Vemes si na to partu delniku, daji to za den. Vemes si na to bagr, hrabne 4x a ma to za pul hodiny. Rozdilny algoritmus. Ale aby sel pouzit bagr, musis mit kolem dostatek prostoru, ktery ten bagr muze pojezdit, znicit a ne souseduv pestovany travnicek.

#1 Bius
Časová a paměťová složitost jsou dva pojmy, které jsou úplně na opačné straně spektra. Většinou platí pravidlo, čím chceš menší časovou složitost, tím větší bude ta paměťová a naopak.

Jak paměťovou složitost určit? Pokud ti jde o reálná data, stejně jako časovou složitost můžeš určit změřením času od začátku do konce běhu algoritmu, paměťová složitost se dá určit podobným způsobem, změřením, kolik MB paměti ti daný algoritmus sežere.

Pokud ti jde spíše o teoretické hodnoty, pak budeš muset daný algoritmus prozkoumat, vyznat se v jazyce, v němž je algoritmus napsaný a na základě zdrojového kódu zjistit, jak je algoritmus náročný (například kdybys měl algoritmus, který ti kopíruje obsah pole do nového, zcela identického a poslal mu n prvků, výsledkem bude, že budeš mít prvků 2n, což je taky paměťová složitost).

Vzhledem k výpočtům ale často paměťová a časová složitost mají stejný přepis, akorát s jinými konstantami, proto se možná ptáš, zda jsou to stejné věci a určují se jedná z druhé, což nejsou.