Zlozitost.. Na co si dat pozor – C / C++ – Fórum – Programujte.com

Zdravim. Prosim vas vysvetlite mi niekto slozitost jednotlivych funkci.. ? na co si davat pozor, aby bola zozitost co najnizsia. Ako na nu ? co robit a co nerobit ? Dakujem za pomoc

Vybral sis C/C++ což už samo je složitej jazyk. Začneš tak, že si seženeš nějakou knížku, případně na netu najdeš nějakej seriál (třeba tady na webu), kde se prokoušeš od základů po to komplikovaný..., ale komplikovanosti se nikdy nevyhneš, ono tedy bude záležet co chceš vytvořit, ale těžko uděláš jednoduše složité věci.

#1 nord
I pokud myslíš časovou/paměťovou složitost, tvůj dotaz je tak šíleně obecný, že ho prostě není možné zodpovědět. Zkonkretizuj příklady.

Ospravedlnujem sa, to bude koli nevedomosti.. ano myslim casovu/pamatovu zlozitost
napr teraz prehladavam zoznamy..
LinkedList a ArrayList. ak chcem co najnizsiu zlozitost tak lajcky povedane.. mal by som sa vyhybat nejakemu vnaraniu cyklov pokial to nie je naozaj nutne? ma na to vplyv aj pocet parametrov danej funkcie ?

#4 nord
Pro algoritmy, datové struktury a složitosti bývá na vysokých školách předmět minimálně jeden celý semestr, a ani tam se nepokryje všechno, protože je to prostě téma tak rozsáhlé.

Navíc se každý problém řeší jinak, takže jakmile narazíš ty na svůj vlastní problém, s největší pravděpodobností na něho nebude jednoznačná kuchařka, jak nejvhodnější řešení uvařit.

Můžeš začít tímto jednoduchým úvodem z ČVUT: první část, druhá část, třetí část, naučit se, co to ta Big-O notace skutečně je, co znamená.

Co se hodně často ovšem stává je, že máš buď jedno nebo druhé, tj. optimální časovou nebo paměťovou složitost, ale zpravidla ne obojí zároveň (tento problém vzniká kvůli nutnosti uchovávat extra navíc k nejnutnějším datům, vedoucí k redundanci, nabývání paměťové složitosti, pro usnadnění například vyhledávání nad danou datovou kolekcí).

Složitost je velmi teoretický pojem a s jako takovým je třeba s ní zacházet a aplikovat ji na možné postupy. Například pokud programuji v C++ a vím, že budu mít kolekci dat, které je možné jednoznačně identifikovat a nebudou se opakovat, data budou unikátní, pak je asi lepší použít std::set než std::vector. A abys toto v daném jazyce věděl, je třeba samozřejmě znát daný jazyk, jeho komponenty a pak, jsme zas u toho, rozumět složitostem daných komponent.

Co se navyšování složitosti týče, tak ano, iterace přes kolekce bývají největším bottleneckem. Ty lze občas zmírnit vhodnější datovou strukturou, například namísto použití lineárního seznamu použiješ nějaký BST, výjimečně je možné je vhodnou konstrukcí zcela eliminovat.

Každopádně v praxi se běžně nějaký foreach vůbec neřeší. Prostě se naprogramuje řešení, aby program fungoval, a teprve poté, když chceš, aby ti proces trval namísto 500 ms jenom 150 ms, se zjišťuje, kde by se proces dal zrychlit.

#5 ondrej39
parada dakujem za vystvetlenie :) pozriem si to teda riadne a dufam ze postupne sa do toho dostanem