Złożoność algorytmu

Odpowiedz Nowy wątek
2014-06-08 23:31
0

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.

Pozostało 580 znaków

2014-06-09 09:19
0

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)

edytowany 4x, ostatnio: xxxmateusz00xxx, 2014-06-09 09:36

Pozostało 580 znaków

2014-06-09 09:30
yarel
0

Mam wrażenie, że ten algorytm pesymistycznie się nie zatrzyma ;) No chyba, że za pierwszym razem trafi w wartość x.

Gdzieś w pamięci trafi na tego x np na samego siebie. - _13th_Dragon 2014-06-09 09:33

Pozostało 580 znaków

2014-06-09 09:37
0

Nie znam sie na pascalu, ale brakuje mi właśnie zwiększania np zmiennej i, czy zmniejszania zmiennej j

edytowany 1x, ostatnio: xxxmateusz00xxx, 2014-06-09 09:37

Pozostało 580 znaków

2014-06-09 09:38
yarel
0

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

Możliwe że problem w tym że to while i &lt;= j and not(f ) then jest niepoprawne po while ma być do poza tym wcięcia sugerują że if jest wewnątrz tego while - _13th_Dragon 2014-06-09 11:14

Pozostało 580 znaków

2014-06-09 09:54
mateusz00
0

Po co w takim razie ten while? Algorytm klasy O(1)?

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0