Občas sa možno stretneš s názorom, že programovanie je vlastne len zamaskovaná matematika. Sčasti je to pravda, ale je tu jeden dôležitý rozdiel. V matematike neexistuje "lepší dôkaz" a "horší dôkaz". Každý korektný postup, ktorým sa dostaneme k výsledku, je rovnako dobrý. V programovaní je to ináč.
Keď riešime nejaké problémy, môže sa stať, že vymyslím viacero riešení. Ako však povedať, ktoré je lepšie a vôbec, čo to znamená byť lepším? O tom všetkom sa porozprávame práve v tejto kapitole.
Dôležitým aspektom je rýchlosť daného algoritmu. To znamená, ako rýchlo sa pre nejaký vstup doráta k výsledku. Nechceme predsa čakať na výsledok niekoľko hodín, ak sa dá vyrátať v priebehu sekúnd. Poďme sa teda zamýšľať nad takzvanou časovou zložitosťou algoritmov.
V praxi sa s potrebou rýchlych algoritmov stretneš úplne na každom kroku. Ked si otvoríš schránku s e-mailami, nechce sa ti asi hodinu čakať, kým ich počítač usporiada a vypíše. Pri vyhľadávaní slova v texte by si tiež chcel od počítača okamžitú odozvu. A aj "vo svete biznisu" je to tak. Napríklad také banky si denne posielajú toľko rôznych správ (napríklad platobných príkazov), že keby ich spracúvanie bolo príliš pomalé, jednoducho by sa im začali hromadiť.
A práve preto sa vymyslela teória, ktorej sa začalo hovoriť časová zložitosť algoritmov. O čo v nej ide? To, čo chceme dosiahnuť, je vedieť o danom algoritme povedať, ako veľa údajov dokáže v rozumnom čase spracovať.
Hneď na začiatku sa však stretávame s množstvom problémov. Prvým je to, že nechceme porovnávať skutočný čas výpočtu. Ten je totiž príliš ovplyvnený počítačom, na ktorom daný program spúšťame. Nečakáme predsa, že na počítači našej babky bude bežať rovnaký algoritmus takisto rýchlo ako na počítači v Googli. Musíme sa teda snažiť oddeliť časovú zložitosť algoritmu od výpočtu na skutočnom počítači. Bolo by teda fajn, ak sme vedeli odhadnúť rýchlosť programu z obyčajného pohľadu naň, bez toho, aby sme ho museli programovať a spúšťať.