Licenca
To delo je na voljo pod pogoji slovenske licence Creative Commons 2.5:
priznanje avtorstva - nekomercialno - deljenje pod enakimi pogoji.
Celotna licenca je na voljo na spletu na naslovu http://creativecommons.org/licenses/by-nc-sa/2.5/si/. V skladu s to licenco je dovoljeno vsakemu uporabniku delo razmnoževati, distribuirati, javno priobčevati, dajati v najem in tudi predelovati, vendar samo v nekomercialne namene in ob pogoju, da navede avtorja oziroma avtorje in izdajatelja tega dela. Če uporabnik delo predela, kar pomeni, da ga spremeni, preoblikuje, prevede ali uporabi to delo v svojem delu, lahko predelavo dela ponudi na voljo le pod pogoji, ki so enaki pogojem iz te licence oziroma pod enako licenco.
Pri vseh teh poskusih imamo sicer enako velike primerke problema – n = 100, kajti tabela a ima vsakič po 100 števil – vendar je čas izvajanja od primera do primera zelo različen. Naša funkcija NajdiVsoto se neha izvajati, čim najde par elementov z vsoto a[i] + a[j] = s, torej je čas izvajanja zelo odvisen od tega, kako hitro najde prvi tak par. V najslabšem primeru (če para elementov z vsoto s sploh ni) mora funkcija pregledati čisto vse možne pare (do tega je na primer prišlo, ko smo imeli a = [0, 1, ..., 99] in s = 12345; do vsote 12345 pri tej tabeli a sploh ne moremo priti, saj je največja možna vsota dveh elementov v njej le 98 + 99 = 197).
Vidimo torej, da ko smo prej govorili o T(n) kot o času izvajanja na primerku problema velikosti n, je ta pojem pravzaprav precej nejasen. Primerkov problema velikosti n je veliko in čas izvajanja je na različnih primerkih lahko zelo različen. Praviloma nas pri razmišljanju o časovni zahtevnosti nekega postopka zanima predvsem to, kaj se lahko zgodi v najslabšem primeru, zato za T(n) uporabimo najdaljši čas izvajanja po vseh primerkih problema velikosti n. Tega se bomo držali tudi v našem učbeniku. (Druga možnost je, da bi za T(n) vzeli nekakšno povprečje po vseh primerkih velikosti n, vendar se v praksi ponavadi izkaže, da je veliko težje oceniti takšno povprečje kot maksimum.)
Različno hitri algoritmi za isti problem
Funkcijo NajdiVsoto, ki smo jo uporabljali doslej, bi se dalo še izboljšati. Naša dosedanja funkcija mora za vsak par indeksov i in j izračunati vsoto a[i] + a[j] ter jo primerjati s številom s. Tu imamo torej dva dostopa do tabele a (operatorji []), eno seštevanje in eno primerjanje.
Do malo hitrejše rešitve pridemo, če si pogoj a[i] + a[j] == s predstavljamo drugače: ta pogoj pravzaprav preverja, če a[j] upošteva razliko (del, ki številu a[i] še manjka do s). Z drugimi besedami, enakovreden pogoj je a[j] == s - a[i]. Ta razlika s - a[i] pa ni odvisna od j, ampak le od i.
Ko se torej pri istem i (v isti iteraciji zunanje zanke) pomikamo po različnih j, nam te razlike ni treba računati vsakič sproti; dovolj je že, če jo izračunamo le enkrat pri vsakem i. Tako dobimo naslednjo rešitev:
Zdaj imamo torej pri vsakem paru indeksov i in j le dve operaciji namesto štirih: en dostop do tabele a in eno primerjanje. Zato si lahko predstavljamo, da se bo izvajala približno pol manj časa kot prvotna rešitev, saj se drugače obe funkciji obnašata enako – obe morata obdelati enako število parov (i, j).