Časovna zahtevnost

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.

to je odgovor za drug primer?

kako pa je v primeru da imam seznam?

torej ima sklad tudi O(n)?

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

najlepša hvala za odgovore

WOT?

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

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

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.

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

Jasno da je.