Dany jest algorytm:
ALG(A[1..n],x)
f := false
i := 1
j := n
while i <= j and not(f ) then
m := (i+j) div 2
if A[m]=x then f true
else if x>A[m] then m := m+1
else m := m-1
return f
a)określ pesymistyczną złożoność algorytmu ze wzgledu na porównania.
b)podaj dokładną pesymistyczną złożoność ze wzgledu na podstawienia.
c)podaj rząd złożoności algorytmu
a) to będzie n/2?
b) n?
c) nie mam pojęcia.
z góry dziękuję za pomoc.
a) w while masz 2 porównania, w ifach masz dwa porównania O(4n)
b) przed while 3 podstawienia (tylko raz podstawiamy), po while (w petli za kazdym razem) masz jedno podstawie, i po ifach moze tez byc jedno O(2n) + 3
c) algorytm jest klasy O(n)
niech mnie ktos poprawi jesli sie myle
EDIT: mala poprawka w b), a co do c) to prosze niech ktoś spojrzy na algorytm dokładniej czy przypadkiem nie jest klasy O(log n)
Mam wrażenie, że ten algorytm pesymistycznie się nie zatrzyma ;) No chyba, że za pierwszym razem trafi w wartość x.
Nie znam sie na pascalu, ale brakuje mi właśnie zwiększania np zmiennej i, czy zmniejszania zmiennej j
@ _13th_Dragon możesz rozwinąć temat pamięci? Z pseudokodu wynika, że algorytm strzela w "środek tablicy" i albo trafia, albo nie. Nie widzę, gdzie miałby wyjechać poza tablicę.
Po co w takim razie ten while? Algorytm klasy O(1)?