Forum » Programiranje » Časovna zahtevnost
Časovna zahtevnost
abcd123 ::
Pozdravljeni,
imam vprašanje glede časovne zahtevnosti.
Kolikšen je v splošnem red rasti časovne zahtevnosti algoritma iskanja z bisekcijo?
Odgovor: O(log n)
Je to pravilno?
Kolikšen je v splošnem red rasti časovne zahtevnosti iskanja podatka v iskalnem drevesu?
Pri tem pa sem našel, da je odgovor naslednji:
V najboljšem primeru je O(log n), v najslabšem pa O(n).
Kakšen je torej pravilen odgovor na zgornje vprašanje?
Najlepša hvala za odgovore.
imam vprašanje glede časovne zahtevnosti.
Kolikšen je v splošnem red rasti časovne zahtevnosti algoritma iskanja z bisekcijo?
Odgovor: O(log n)
Je to pravilno?
Kolikšen je v splošnem red rasti časovne zahtevnosti iskanja podatka v iskalnem drevesu?
Pri tem pa sem našel, da je odgovor naslednji:
V najboljšem primeru je O(log n), v najslabšem pa O(n).
Kakšen je torej pravilen odgovor na zgornje vprašanje?
Najlepša hvala za odgovore.
Sergio ::
Pravilen odgovor je O(log2 n). (Torej: O od dvojiskega logaritma od n).
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
fiction ::
Če vzameš iskalno drevo, moraš za spodnjo asimpotitčno mejo vzeti najslabši primer in to je takrat, ko se ti drevo izrodi v seznam (torej da ima vsako vozlišče enega potomca). Seveda pa je drugače, če lahko predpostaviš, da bo drevo vedno uravnoteženo (če imaš npr. rdeče-črno, AVL drevo ali kaj podobnega).
Bisekcijo si tudi lahko predstavljaš kot neke vrste binarno iskalno drevo, ki je lepo uravnoteženo, višina od takega drevesa je log2n (na vsakem koraku odrežeš "pol").
Kar se tiče seznama je dokaj intuitivno, da moraš v najslabšem primeru čez vse (n) elemente, v povprečju boš našel element že nekje na polovici (n/2), ampak ker konstantni faktor zanemariš in te zanima samo red je to še vedno O(n). Tako je tudi log2n v bistvu O(logn).
Bisekcijo si tudi lahko predstavljaš kot neke vrste binarno iskalno drevo, ki je lepo uravnoteženo, višina od takega drevesa je log2n (na vsakem koraku odrežeš "pol").
Kar se tiče seznama je dokaj intuitivno, da moraš v najslabšem primeru čez vse (n) elemente, v povprečju boš našel element že nekje na polovici (n/2), ampak ker konstantni faktor zanemariš in te zanima samo red je to še vedno O(n). Tako je tudi log2n v bistvu O(logn).
fiction ::
Neka podatkovna struktura nima "časovne zahtevnosti". Zanima te koliko trajajo posamezne operacije, ki jih lahko izvajaš. V tem kontekstu lahko rečeš, da je seznam O(n), ker je npr. iskanje elementa ena izmed najbolj počasnih operacij.
Pri skladu pa praviloma samo dodajaš element na vrh (push), brišeš zgornji element (pop) oz. pogledaš kaj je na vrhu (peek), kar je vse O(1). Seveda te lahko tudi zanima, če je nek element vsebovan, ampak to pa potem zelo verjetno traja O(n) časa in v takem primeru ne vem zakaj bi sploh potreboval sklad.
Edit: log2n = log2 n, ne log(2n).
Pri skladu pa praviloma samo dodajaš element na vrh (push), brišeš zgornji element (pop) oz. pogledaš kaj je na vrhu (peek), kar je vse O(1). Seveda te lahko tudi zanima, če je nek element vsebovan, ampak to pa potem zelo verjetno traja O(n) časa in v takem primeru ne vem zakaj bi sploh potreboval sklad.
Edit: log2n = log2 n, ne log(2n).
Zgodovina sprememb…
- spremenil: fiction ()
technolog ::
technolog ::
Ja ni važno kakšno osnovo napišeš pri logaritmu, pomeni enako.
To je pač posledica tega, da računalničarji nimate pojma o matematiki.
To je pač posledica tega, da računalničarji nimate pojma o matematiki.
Zgodovina sprememb…
- spremenil: technolog ()
usoban ::
je res, ker se gleda samo red.
Vir: Time complexity @ Wikipedia
An algorithm is said to take logarithmic time if T(n) = O(log n). Due to the use of the binary numeral system by computers, the logarithm is frequently base 2 (that is, log2 n, sometimes written lg n). However, by the change of base equation for logarithms, loga n and logb n differ only by a constant multiplier, which in big-O notation is discarded; thus O(log n) is the standard notation for logarithmic time algorithms regardless of the base of the logarithm.
Vir: Time complexity @ Wikipedia
Spura ::
Sergio ::
@technolog: Ja, ker nimamo pojma o matematiki, in ker velja da O(log2 n)=O(log10 n), so vsa B-drevesa kar naenkrat postala binarna drevesa :). Sej je itak vse isto.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Spura ::
mislim da matematiki ne znajo racunalnistva in so nas vse nategnil, da je najpomembnejsa metrika casovne zahtevnosti njena asimptota, ker itak vsi operiramo z neskoncnimi dataseti.
technolog ::
Ne gre za to, gre za to da na majhnih datasetih ne moreš ničesar rečt.
Edina logična mera je kako se potreben čas spreminja z velikostjo vhoda, neodvisno od programskega jezika, procesorja, operacijskega sistema, etc...
Obstajajo tud druge metrike, ampak imajo zelo ozke uporabe.
Edina logična mera je kako se potreben čas spreminja z velikostjo vhoda, neodvisno od programskega jezika, procesorja, operacijskega sistema, etc...
Obstajajo tud druge metrike, ampak imajo zelo ozke uporabe.
JanK ::
@technolog: Ja, ker nimamo pojma o matematiki, in ker velja da O(log2 n)=O(log10 n), so vsa B-drevesa kar naenkrat postala binarna drevesa :). Sej je itak vse isto.
Big O notation @ Wikipedia
Let k be a constant. Then:
O(kg) = O(g) if k is nonzero.
log10(n) = log2(n)/log2(10) = 1/log2(10) * log2(n)
1/log2(10) je seveda konstanta
O(log10(n)) = O(1/log2(10)*log2(n)) = O(log2(n))
QED
"Think about how stupid the average person is,
then realize that 50% are stupider than that"
-George Carlin
then realize that 50% are stupider than that"
-George Carlin
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Podatkovna struktura potekaOddelek: Programiranje | 875 (637) | smacker |
| » | Za programerske teoretikeOddelek: Programiranje | 8798 (5600) | Jerry000 |
| » | [Naloga] - Algoritmi, časovna kompleksnostOddelek: Programiranje | 6994 (3180) | WarpedGone |
| » | [C++] Podatkovne Strukure - KombinacijeOddelek: Programiranje | 1092 (1092) | BigWhale |
| » | Grafi (Kruskal, Dijkstra,...)Oddelek: Programiranje | 2386 (2269) | Realist |