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.
Različno hitri algoritmi
Postavimo se v mislih na nek konkreten i in poiščimo zadnji tak j, pri katerem vsota a[i] + a[j] še ni prevelika (večja od s). Funkcija NajdiVsoto2b bi torej pri tem i pregledala vsote a[i] + a[i + 1], a[i] + a[i + 2], ..., a[i] + a[j]; in vse te vsote so ≤ s. Ker je tabela a urejena naraščajoče, so tudi te vsote naraščajoče; torej, če je ena od njih enaka s, bi morale biti vse nadaljnje vsote večje od s, mi pa smo ravnokar ugotovili, da so vse te vsote ≤ s. Edina vsota, ki je lahko enaka s, je torej zadnja – a[i] + a[j] – vse predhodne vsote pa so gotovo manjše od s.
Pregledovati vsote, ki so premajhne (manjše od s), je seveda prav tako nekoristno kot pregledovati tiste, ki so prevelike. Namesto da gledamo vsote od manjših proti večjim (in začnemo pri a[i] + a[i + 1]), bi bilo bolje le pogledati zadnjo od njih, torej a[i] + a[j]; če je ta enaka s, smo našli iskani par in se lahko vrnemo iz funkcije, če pa je manjša od s, potem so vse predhodne vsote tudi manjše od s in se nam z njimi ni treba ukvarjati.
Toda kako naj vemo, kateri je (pri trenutnem i) pravi j (torej zadnji tak j, pri katerem vsota a[i] + a[j] še ni večja od s)? Pri i = 1 ga lahko poiščemo tako, da gremo v zanki po padajočih j (od j = n - 1 navzdol), dokler ne najdemo prvega para z vsoto a[i] + a[j] <= s. V nadaljevanju pa lahko razmišljamo takole: ko se z i premaknemo na i + 1, je seveda člen a[i + 1] večji od a[i], zato je (za poljuben j) tudi vsota a[i + 1] + a[j] večja od a[j]. Torej, če je bila pri nekem j vsota a[i] + a[j] prevelika (večja od s), bo zdaj ta prevelika vsota a[i + 1] + a[j] še večja. Zato maksimalni j, pri katerem je vsota a[i + 1] + a[j] ≤ s, ne more biti nič večji kot maksimalni j, pri katerem je vsota a[i] + a[j] ≤ s. Torej lahko primerni j pri i + 1 poiščemo tako, da nadaljujemo kar pri tistem j, ki smo ga uporabili pri i, in se po potrebi pomaknemo z njim malo navzdol. Tako smo dobili zelo elegantno rešitev, zapisano na naslednji strani.
Pregledovanje vsot