Dinamično programiranje: Razlika med redakcijama

Izbrisana vsebina Dodana vsebina
mBrez povzetka urejanja
mBrez povzetka urejanja
Vrstica 12:
* pristop nazaj
 
Prednost dinamičnega programiranja je predvsem ta, da kadar želimo delati z več objekti, ne rabimo zanje rezervirati fiksnih količin spomina (glej [[poljetabela (računalništvo)|poljatabela]] (ang. array) ampak ga lahko dodeljujemo dinamično po potrebi. Podatke lahko s kazalci uredimo na primer v vrsto (podatkovni tip) oseb, ki stojijo pred blagajno. Vsak objekt (Oseba) v tej vrsti bo vseboval atribute o sebi ter kazalec na naslednjo osebo. Zadnji objekt bo vseboval kazalec na prazen prostor (null). Kadar dodamo novo osebo v vrsto, dinamično rezerviramo v pomnilniku prostor za novo osebo (ustvarimo nov objekt), ter zadnji osebi spremenimo prazen kazalec na novoustvarjeno osebo. (glej tudi podatkovne strukture seznam, sklad)
Pri [[programiranje|programiranju]] uporabljamo različne [[podatkovni tip|podatkovne tipe]] (odvisno od [[programski jezik|programskega jezika]]. Osnovni so običajno int (integer, celo število), bool (da ali ne), char (znaki, tudi črke). Vsak izmed njih v pomnilniku (strojno) zaseda neko število ničel in enic (bitov). Iz teh lahko gradimo zahtevnejše podatkovne tipe, znane pod imenom [[razred|razredi]] (ang. Class). Gre za podatkovne tipe, kjer enemu [[objekt|objektu]] dodelimo več [[atribut|atributov]]. V primeru razreda 'Oseba' bi bili atributi 'int leto_rojstva', polje znakov 'char[] ime', 'int visina', 'int teza', ... Tako lahko uporabimo kar spremenljivko tipa 'Oseba' in na enem primeru osebe (tukaj že govorimo o objektu) razpolagamo z vsebovanimi atributi. Kadar ustvarimo polje oseb, se v spominu rezervira prostor za vse vsebovane objekte (dimenzija polja). Eden izmed atributov objekta je lahko tudi objekt istega razreda, ali v primeru dinamičnega programiranja pogosteje [[kazalec|kazalec]] (ang. pointer) na objekt istega razreda. S pomočjo kazalcev lahko tako med seboj povezujemo objekte, kar v veliki meri izkoriščajo iskalni algoritmi.
 
Prednost dinamičnega programiranja je predvsem ta, da kadar želimo delati z več objekti, ne rabimo zanje rezervirati fiksnih količin spomina (glej [[polje|polja]] (ang. array) ampak ga lahko dodeljujemo dinamično po potrebi. Podatke lahko s kazalci uredimo na primer v vrsto (podatkovni tip) oseb, ki stojijo pred blagajno. Vsak objekt (Oseba) v tej vrsti bo vseboval atribute o sebi ter kazalec na naslednjo osebo. Zadnji objekt bo vseboval kazalec na prazen prostor (null). Kadar dodamo novo osebo v vrsto, dinamično rezerviramo v pomnilniku prostor za novo osebo (ustvarimo nov objekt), ter zadnji osebi spremenimo prazen kazalec na novoustvarjeno osebo. (glej tudi podatkovne strukture seznam, sklad)
 
Tak način dodeljevanja pomnilnika je zelo pomemben pri algoritmih, ki zahtevajo veliko število operacij nad veliko količino podatkov. Prav tako lahko pri zahtevnejših podatkovnih strukturah kazalci kažejo na več sosednjih objektov in s tem tvorijo drevo (glej binarna odločitvena drevesa (ang. Binary Decision Tree, BDT)). Za optimizacijo iskalnega časa je potrebno podatke že ob vstavljanju umestiti na ustrezno mesto ter včasih tudi spremeniti strukturo drevesa (Bayerjevo drevo, rdeče-črna drevesa, rotacije). Pri tem dinamićno spreminjamo kazalce med objekti.