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.
*Še nekaj redov zahtevnosti
Vaja
Do eksponentne zahtevnosti pogosto pride pri postopkih, ki temeljijo na rekurziji. Recimo, da sestavljamo cikcakasto pot, pri čemer je vsak korak lahko oblike / (gor in desno) ali pa \ (dol in desno). Radi bi prešteli vse take cikcakaste poti, ki so dolge n korakov in ki se končajo k enot višje od začetnega položaja (k je lahko tudi negativen, kar pomeni, da konec črte leži nižje od začetnega položaja). Na primer pri n = 3, k = 1 so take črte naslednje: /\/, \// in
//\.
To nalogo lahko (neučinkovito) rešimo takole:
(a) Dopolni funkcijo StevPoti tako, da v neki globalni spremenljivki šteje, koliko klicev te funkcije se je izvedlo.
(b) Preizkusi funkcijo za različne n in k in se prepričaj, da je njena časovna zahtevnost res eksponentna v odvisnosti od n.
(c) *Razmisli o tem, kako bi se dalo to funkcijo izboljšati, da bi enak rezultat računala hitreje (s polinomsko časovno zahtevnostjo namesto z eksponentno).
Primer
Po drugi strani pa obstajajo tudi postopki s časovno zahtevnostjo, ki je manjša od katerekoli polinomske. Oglejmo si na primer naslednji postopek, ki dobi urejeno tabelo a in poišče, kje v njej se pojavlja število x: