» »

Č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.

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.

abcd123 ::

to je odgovor za drug primer?

genesiss ::

Za oba. (Če je iskalno drevo dvojiško)

abcd123 ::

kako pa je v primeru da imam seznam?

genesiss ::

O(n) v splošnem (enojno povezan seznam)

Zgodovina sprememb…

  • spremenil: genesiss ()

abcd123 ::

torej ima sklad tudi O(n)?

genesiss ::

Kaj misliš?

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).

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).

Zgodovina sprememb…

  • spremenil: fiction ()

abcd123 ::

najlepša hvala za odgovore

technolog ::

Sergio je izjavil:

Pravilen odgovor je O(log2 n). (Torej: O od dvojiskega logaritma od n).


O(log2 n)

je enako

O(log10 n)

_Dormage_ ::

WOT?

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.

Zgodovina sprememb…

usoban ::

je res, ker se gleda samo red.

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 ::

technolog je izjavil:

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.

Ja itak, ne znamo srednjesolske matematike. Bogi smo.

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.

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.

JanK ::

Sergio je izjavil:

@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

GhostMB ::

Potem je O(log2 n) isto kot O(log n) ali ne??

Senitel ::

Da (log n = loge n).

technolog ::

Jasno da je.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Podatkovna struktura poteka

Oddelek: Programiranje
5827 (589) smacker
»

Za programerske teoretike

Oddelek: Programiranje
478587 (5389) Jerry000
»

[Naloga] - Algoritmi, časovna kompleksnost

Oddelek: Programiranje
246901 (3087) WarpedGone
»

[C++] Podatkovne Strukure - Kombinacije

Oddelek: Programiranje
61048 (1048) BigWhale
»

Grafi (Kruskal, Dijkstra,...)

Oddelek: Programiranje
92291 (2174) Realist

Več podobnih tem