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.
Implementacija s tabelo elementov
Zaporedje lahko na enostaven in naraven način predstavimo (implementiramo) s tabelo njegovih elementov. Elemente zaporedja v tabelo preprosto zapišemo po vrsti, potem pa do njih dostopamo s pomočjo indeksov (prvi element ima indeks 0, drugi 1 itd.). Recimo zaporedje z elementi 'O', 'D', 'E' in 'R' predstavimo s tabelo ['O', 'D', 'E', 'R']. Vrstni red elementov v tabeli je seveda natančno določen, prav tako pa se elementi v njej lahko ponavljajo. Tabela elementov torej podpira obe ključni lastnosti zaporedja. Ker smo najpomembnejše operacije za delo s tabelami že spoznali, jih s pomočjo naslednje naloge zgolj na hitro ponovimo:
Vaja
Kaj izpiše spodnji program? Nalogo najprej reši na papir, nato pa rezultat preveri s pomočjo interaktivnega tolmača:
Kako učinkovite so posamezne operacije? Njihova časovna zahtevnost je odvisna od predstavitve tabele v računalnikovem pomnilniku. Ta pa je sila enostavna: v pomnilniku so namreč elementi tabele nanizani eden za drugim, vsi pa zavzemajo enako količino pomnilniškega prostora (npr. b bajtov). Če poznamo pomnilniški naslov prvega elementa tabele (npr. p), potem vemo, da se element z indeksom i nahaja na naslovu p + i · b. Za lažjo predstavo je na spodnji sliki prikazan primer za p = 200 in b = 8:
Pomnilniški naslov elementa z indeksom i se vedno izračuna s preprostim množenjem in seštevanjem, ne glede na trenutno število elementov v tabeli. To pomeni, da je časovna zahtevnost operacije dostopa do posameznega elementa tabele (torej operacije tabela[indeks]) enaka O(1).
Python poleg samih elementov tabele hrani tudi število elementov (dolžino tabele), kar pomeni, da se funkcija len prav tako izvrši v času O(1). Tudi časovna zahtevnost dodajanja na konec tabele je neodvisna od števila elementov v tabeli, saj se pomnilniški naslov, kamor se doda novi element, izračuna enostavno kot p + n · b, pri čemer je n trenutno število elementov. (Python za tabelo vnaprej rezervira določen del pomnilniškega prostora. Ko se ta prostor zapolni, mora rezervirati nov, večji del prostora in elemente tabele prekopirati vanj. Ta operacija traja O(n) časa, vendar pa je razmeroma redko potrebna, zato je povprečna časovna zahtevnost dodajanja elementov na konec tabele še vedno enaka O(1).)
Povsem drugače pa je z dodajanjem na začetku ali sredini, saj je treba v ta namen vse elemente od položaja vstavljanja do konca tabele prestaviti za eno mesto v desno. Na primer, če želimo na začetek tabele znakov ['O', 'D', 'E', 'R'] vstaviti znak 'M', potrebujemo štiri premike (glej sliko na naslednji strani!).