Amit tudnod kell fejlesztőként, II. rész: Algoritmusok és komplexitás
A "régi" időkben egy programozónak elengedhetetlen volt a különböző algoritmusok és adatstruktúrák implementációs részleteinek ismerete. A mai nyelvek többsége már tartalmaz implementációkat a gyakran előforduló problémákra (tárolás, rendezés, stb.), azonban ez nem jelenti azt, hogy ezek az ismeretek feleslegesek lennének, sőt.
Ennek egyik oka, hogy hiába tartalmaznak a szabványos könyvtárak sok jól megírt algoritmus-implementációt, ettől még tudnunk kell, milyen feladatra melyik a legoptimálisabb. A másik ok, hogy ezek az implementációk bár számos esetben kiválóak, mindig vannak olyan problémák, amelyre önálló megoldással kell előállnunk. Továbbá minél több algoritmust ismerünk (legalább input, output, komplexitás szintjén), annál nagyobb az esélye, hogy egy szembejövő új problémát le tudunk fordítani egy már ismert módszerre.
Nagyon fontos, hogy képesek legyünk komplexitás szempontjából elemezni a saját kódunkat, és másokét is. Az algoritmusok "teljesítményének", komplexitisának leírására a nagy ordó jelölést használjuk — ezzel a szükséges idő és tárhely egyaránt leírható a bemenet nagyságának függvényében.
Mivel a témával vastag könyveket lehet megtölteni, a bővebb ismertetésre itt nincs mód, aki főiskolán, egyetemen nem tanulta volna (vagy nem emlészik rá), annak mindenképpen érdemes elolvasnia legalább egy rövid összefoglalót (például ezt).
Röviden nézzünk egy példát azért (mindenféle tudományos igényesség nélkül). Az n méretű bemenetre O(n) időigényű algoritmus futásideje a bemenet növekedésével lineárisan növekszik — például egy ezerelemű tömbben való keresés (megközelítőleg) tízszer annyi ideig tart, mint egy százeleműben. Egy O(n2) időigényű algoritmusnál ugyanez már négyzetes: egy ezerelemű tömböt nem tízszer annyi ideig tart rendezni, mint egy százeleműt, hanem százszor (hangsúlyozni kell, hogy nem pontosan négyzetes az arány, ez csak a nagyságrendre utal). Amint az elején említettem, fontos ismernünk a gyakori algoritmusok komplexitását, hogy a saját problémánknak megfelelően a legjobbat tudjuk kiválasztani. Ehhez jó segítség ez a cheat sheet, ami sok alap algoritmus teljesítményét gyűjti össze egy oldalon. Egy kis gyakorlattal saját algoritmusaink idő-, és memóriaigényét is könnyen meg tudjuk becsülni.
Nagyon fontos az is, hogy minél több létező problémára ismerjünk algoritmusokat: rendezések, keresések, adatstruktúrák, gráfok. Az utóbbit különösen érdemes kihangsúlyozni: egy-egy bonyolultabbnak tűnő probléma rengeteg esetben a gráfok nyelvére fordítható, ez esetben pedig algoritmusok óriási óceánja áll rendelkezésünkre. Ha nem tudod, mik a gráfok, gyakorlatilag bármilyen számításelméleti könyvben megismerkedhetsz velük. A gyakorlatban nem feltétlenül fontos az implementáció-szintű ismeret; sokszor az is elegendő, ha tudjuk, hogy egyáltalán létezik az adott módszer, és nem kezdjük el feltalálni a spanyolviaszt.
Mindent egybevetve az algoritmusok és a komplexitáselmélet legalább alapszintű ismerete a programozás olyan alapkövei közé tartozik, amelynek megfelelő ismeretét nem lehet eléggé hangsúlyozni — már csak azért sem, mert állásinterjúkon is gyakori téma.