Představte si, že stejně jako ostatní členové kapely si máte najít daných 40 skladeb z neseřazené složky asi 200. Tak začnete hledat první skladbu, dáte ji stranou, potom od začátku zase druhou skladbu, dokud nemáte všech 40, na tom přece nic není. Nebo by to snad šlo udělat nějak líp?
V popsané situaci se Roger Dannenberg, trumpetista, zachoval spíš jako informatik. Odhadl, že množství těch papírů stojí za rychlou úvahu. Zatímco všichni ostatní začali postupně procházet složku a po jedné hledat a vybírat skladby, Dannenberg se rozhodl nejprve složku s dvěma sty skladbami seřadit.
Abychom mohli jeho přístup s ostatními porovnat, potřebujeme nějakou “měrnou jednotku”. Pro zjednodušení budeme počítat, kolikrát je potřeba vzít do ruky papír se skladbou a porovnat její název s nějakým jiným (nebo stejným). Když se řadí chytře, je potřeba řádově nanejvýš N·log2(N) takových porovnání. Parametr N je počet řazených věcí, v našem případě velikost složky, takže 200. Můžeme tedy odhadnout 200·8 = 1600 porovnání (200 je někde mezi 128 a 256, logaritmus 200 je mezi 7 a 8). To je docela hodně, a skutečně, on pořád ještě řadil, zatímco ostatní byli zpola hotovi a podivovali se jeho počínání.
Teprve v seřazené složce pak Dannenberg hledal konkrétní skladby. Jako informatik to opět dělal optimálně, takže každou skladbu jistě našel nejpozději na osmé podívání (porovnání). Skladeb hledal 40, využil tedy přinejhorším 40·8 = 320 porovnání. Celkově pak pro celý úkol 1600+320 = 1920 porovnání.
Ostatní hledali v neseřazené složce a museli proto kontrolovat každý jeden list, dokud skladbu po průměrně 100 porovnáních nenašli. Celkově tak potřebovali 40·100 = 4000 porovnání. Trumpetista Dannenberg skončil pohodlně jako první.
Uvedné výpočty jsou samozřejmě jen odhady. Možná sami odhalíte, co všechno jsme zjednodušili a zanedbali. Dostatečně ale ilustrují, jaký rozdíl způsobí snaha o efektivní postup podpořená základními znalostmi. Dannenberg navíc téměř jistě nic takového nepočítal, využil prostě zkušenost a intuici. Kdyby bylo not k vyhledání víc, rozdíl by byl ještě větší.
Teď když už jsou všechny skladby nalezeny, máme víc času se v klidu zamyslet. Nemohli bychom postupovat ještě lépe? Předchozí odhady ukázaly, jakou sílu má počet skladeb ve složce. Co kdybychom zkusili minimalizovat počet průchodů touto složkou? Ideálně tak, abychom na každou skladbu “sáhli” pouze jednou? Postup hledání by se tak obrátil: pro každou skladbu ve složce bychom kontrolovali, jestli patří mezi hledané. Takový postup není vůbec intuitivní, ale podívejme se, jak obstojí vůči předchozím.
Abychom si hledání usnadnili, předem bychom seřadili seznam hledaných skladeb (za 40·log240 kroků, odhadněme jako 240). Jedna kontrola v takto seřazeném seznamu si pak vyžádá nanejvýš 6 kroků. Celkem bychom tedy dostali 240+200·6 = 1440 kroků, aspoň takhle v teorii tedy jaště lepší postup, než použil náš trumpetista-informatik.
Nakonec si povšimněme, že v popsané situaci nejde bezmyšlenkovitě použít postupy známé z informatiky. Informatici umí dobře vyhledávat a řadit posloupnosti čísel v pracovní paměti. Jenom když dobře rozumí tomu, proč a jak ty osvědčené algoritmy fungují, mohou je přizpůsobit zcela jiným podmínkám - např. jinému fungování pracovní paměti člověka a tomu, že má dvě ruce.
Dan Lessner, blog Učíme informatiku
