Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Vremenska i prostorna analiza algoritama. Pomoc

[es] :: C/C++ programiranje :: C/C++ za početnike :: Vremenska i prostorna analiza algoritama. Pomoc

[ Pregleda: 2466 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

ericclapton

Član broj: 321798
Poruke: 1
*.dynamic.isp.telekom.rs.



Profil

icon Vremenska i prostorna analiza algoritama. Pomoc06.03.2014. u 20:30 - pre 78 meseci
Ako neko moze malo da mi pojasni pre svega prostornu slozenost algoritama, bila bih veoma zahvalna.
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1227



+92 Profil

icon Re: Vremenska i prostorna analiza algoritama. Pomoc07.03.2014. u 11:14 - pre 78 meseci
Programi su implementacije algoritama. Programi zahtevaju određenu količinu računarske memorije da bi mogli da se izvršavaju, i potrebno im je određeno vreme da bi obavili ono za šta su napravljeni. Ako je svrha programa da obradi veliku količinu podataka onda se ponekad javlja problem da je programu potrebno mnogo memorijskog prostora. Ako imaš dva algoritma koji rade istu stvar, ali se razlikuju po zauzeću memorije, onda ćeš možda želeti da koristiš onaj koji troši manje prostora.

Zamisli, na primer, da imaš neki graf (često implementiran kao matrica u programima). Broj čvorova u grafu (to jest veličina matrice) je, šta znam, jedan bilion. Postoje takvi problemi, samo što ih nećeš videti u školi. Podaci o grafu su smešteni u jednom ogromnom fajlu. E sad, imaš algoritam A koji zahteva da se prvo pročitaju svi podaci, pa da se onda tu nešto obrađuje, i zato ovaj algoritam ima prostornu kompleksnost O(n). Imaš i algoritam B, koji nema takav zahtev, nego s njim prosto učitavaš podatak po podatak, i radiš sa njim šta treba, i kad učitaš sledeći podatak, onaj prethodni si već zaboravila. Ovaj algoritam B ima prostornu kompleksnost O(1). Ako je ovo n malo onda je svejedno koji algoritam ćeš koristiti, a možda je A i brži, zbog načina na koji radi, ali ako je n ogromno onda nemaš izbora nego da koristiš algoritam B, zato što ima manju prostornu kompleksnost.
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: Vremenska i prostorna analiza algoritama. Pomoc

[ Pregleda: 2466 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.