Razlika med hitrostjo delovanja funkcij NajdiVsoto in NajdiVsoto2 (ki je le za nek konstanten faktor – ena je pač dvakrat hitrejša od druge) je zato v nekem smislu zanemarljiva v primerjavi z razliko med hitrostjo teh dveh funkcij in hitrostjo funkcije NajdiVsoto3 (kajti ta razlika se veča sorazmerno z velikostjo n). Do dvakrat hitrejšega izvajanja bi lahko načeloma vedno prišli z zamenjavo računalnika, programskega jezika in podobno – do n-krat hitrejšega izvajanja za poljubno velik n pa na ta način ne moremo priti.

Zato nas, ko razmišljamo o hitrosti delovanja nekega postopka, ponavadi bolj kot sam čas izvajanja zanima to, kako hitro čas izvajanja narašča v odvisnosti od velikosti primerka problema. Temu pravimo red časovne zahtevnosti in ga pogosto označimo z velikim O. Tako na primer rečemo, da imata funkciji NajdiVsoto in NajdiVsoto2 časovno zahtevnost reda O(n2), ker čas izvajanja pri teh dveh funkcijah narašča sorazmerno s kvadratom n; funkcija NajdiVsoto3 pa ima časovno zahtevnost reda O(n), ker čas izvajanja pri njej narašča sorazmerno s samim n.

Razlike, ki jih je le za nek konstanten faktor (kot je na primer razlika med NajdiVsoto in NajdiVsoto2), pa pri razmišljanju o časovni zahtevnosti postopka zanemarimo.

Štetje osnovnih operacij

Doslej smo merili čas izvajanja funkcij v sekundah in že opozorili na nekatere težave (npr. nenatančnost takšnih meritev). Druga težava je, da je dobljene rezultate težko primerjati. Če isti program zaženemo v nekem drugem računalniku in izmerimo čas izvajanja tam, bomo dobili drugačne rezultate; podobno tudi, če ostanemo pri istem računalniku, vendar uporabimo kak drug tolmač pythona; ali pa če isti postopek implementiramo v različnih programskih jezikih, ga prevajamo z različnimi prevajalniki, različnimi nastavitvami in tako naprej.


Takšne meritve so mogoče lahko koristne, če bi radi primerjali hitrosti različnih računalnikov, prevajalnikov, tolmačev ipd. med sabo; če pa hočemo predvsem razumeti, kako hiter je naš postopek (mogoče v primerjavi z nekim drugim postopkom za reševanje istega problema), nam merjenje časa v sekundah le zamegli sliko.

Izvajanje programa si lahko predstavljamo kot dolgo zaporedje nekih osnovnih korakov – preprostih operacij na posameznih vrednostih (celoštevilskih, logičnih ipd.), prireditev takšnih vrednosti, dostopov do elementov tabele ipd. Za oceno časovne zahtevnosti takšnega postopka je čisto dovolj, če približno ocenimo število takšnih osnovnih operacij, v dejanski čas izvajanja posamezne operacije pa se nam ni treba poglabljati. Če na primer nek algoritem reševanje problema velikosti n potrebuje n2 seštevanj, 2n prireditev in n primerjanj, bo časovna zahtevnost tega algoritma reda O(n2) ne glede na to, koliko (nano)sekund traja posamezno seštevanje, posamezna prireditev in posamezno primerjanje.

Lepo pri tem je, da lahko število takšnih osnovnih operacij pri marsikaterem postopku približno ocenimo že s preprostim razmislekom in tako brez veliko merjenja in preizkušanja dobimo občutek za časovno zahtevnost tega postopka. Oglejmo si na primer še enkrat funkcijo NajdiVsoto:

Izvedi Počisti