Različno hitri algoritmi

Vaja

Do še boljše rešitve pa pridemo z naslednjim razmislekom. Spomnimo se, da nam naloga, ki jo rešujemo, zagotavlja, da bo tabela a urejena naraščajoče. (Doslej se na ta podatek nismo opirali – pravzaprav obe dosedanji rešitvi, NajdiVsoto in NajdiVsoto2, delujeta tudi za neurejene tabele.) Recimo, da smo pregledali nek konkreten par elementov tabele a in izračunali vsoto a[i] + a[j]. Če se izkaže, da je ta vsota prevelika (torej večja od s), lahko razmišljamo takole: če bi namesto elementa a[j] uporabili enega od elementov za njim (torej a[j + 1], a[j + 2] itd.), bo ta prevelika vsota še večja, saj so vsi ti kasnejši elementi večji od a[j]. Torej z nobenim od tistih j, ki jih pri trenutem i še nismo pregledali, ne bomo dobili iskane vsote; zato lahko nad trenutnim i kar takoj obupamo in se posvetimo naslednjemu. Tako smo dobili:

Ta izboljšava sicer ne škoduje, res pa je, da v najslabšem primeru tudi ne koristi – lahko se na primer zgodi, da dobimo tako velik s, da pogoj a[i] + a[j] > s sploh nikoli ni izpolnjen, zato do predčasne prekinitve notranje zanke nikoli ne pridemo. Vseeno pa je ta rešitev dobra osnova za naslednjo izboljšavo (ki pa bo koristna).