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
Poleg časovnih zahtevnosti reda O(n) (linearna) in O(n2) (kvadratna), ki smo ju videli v tej učni enoti, so seveda možne tudi druge, na primer O(n3), O(n4) in podobno. Zahtevnosti oblike O(nc), pri katerih je c neka konstanta, z eno besedo imenujemo polinomske.
Vaja
Kakšna je časovna zahtevnost naslednje funkcije, ki vrne dolžino najdaljšega palindromnega podniza v danem nizu s? (Palindrom je tak niz, ki se od konca proti začetku bere enako kot od začetka proti koncu.) Za velikost problema n uporabi dolžino vhodnega niza s.
Za vsak n opiši tudi, pri kakšnem nizu dolžine n bi bila ta najslabša možna časovna zahtevnost tudi dejansko dosežena.
Vaja
Napiši postopek, ki reši problem iz prejšnje naloge (iskanje najdaljšega palindromnega podniza) z manjšo časovno zahtevnostjo.
Še veliko hujše pa so časovne zahtevnosti oblike O(2n), O(3n) in v splošnem O(cn) (za konstanten c); te imenujemo eksponentne (ker imajo velikost problema, n, v eksponentu). Eksponentna zahtevnost narašča (pri dovolj velikih n) hitreje od vsake polinomske in postopki z eksponentno zahtevnostjo so v praksi ponavadi neuporabno počasni, razen mogoče za zelo majhne n. Zahtevnost O(2n) na primer pomeni, da če se n poveča za 1, se čas izvajanja kar podvoji (ker je 2n+1 = 2n · 21 = 2n · 2).