Złożoność algorytmu

[gosia301]

ALG(A[1..n],x)
f ← false
i ← 1
j ← n
while i ≤ j and (not f ) do
m ← (i + j) div 2
if A[m]=x then f ← true
else if x > A[m] then i ← m+1
else j ← m – 1
return f

a) Podaj dokładną pesymistyczną złożoność czasową algorytmu ALG ze względu na porównania
b) Podaj dokładną pesymistyczną złożoność czasową algorytmu ALG ze względu na podstawienia
c) Podaj rząd złożoności pamięciowej algorytmu ALG. UWAGA: Podane odpowiedzi uzasadnij.

[kadiii]

Jest to algorytm binarnego poszukiwania. Wsk. W każdym obiegu petli poszukujemy w zbiorze o połowę mniejszym(z dokładnością do części całkowitej).

[MGT]

optymistyczny jest O(1), bo można trafić od razu.

z oszacowaniem pesymistycznego trochę gorzej, bo to zależy, czy tablica A jest posortowana, bo jeśli nie, to ta pętla może być chyba nieskończona ;p (późno jest, mogę bzdury mówić )
Zakładając, że A jest uporządkowane, to mamy standardowe "dziel i zwyciężaj" i złożoność O(logn).

[spajder]

Wyszukiwanie binarne nie działa na tablicach nieposortowanych (tzn. może produkować błędne wyniki, ale jak najbardziej się zakończy). Natomiast maksymalna ilość wykonań to \(\displaystyle{ \lceil \log_2{n}\rceil]}\) wykonań pętli, trzeba jeszcze zliczyć instrukcje wewnątrz każdej pętli (w założeniu, że poszukiwany element nie istnieje)

[MGT]

Z tym brakiem zakończenia namieszałem (w warunku jest and, a nie or ;p). Niemniej jednak w treści nie napisano, że A jest jakkolwiek uporządkowane, więc algorytm może zakończyć się niepowodzeniem po takiej ilości porównań, jak napisano powyżej.

[kadiii]

Myślę, że powzięcie założenia o uporządkowaniu w zbiorze jest jak najbardziej na miejscu. Inaczej ten algorytm nie robiłby nic sensownego. Np. ciekawe byłoby stwierdzanie złożoności w rekurencji do problemu Collatza(może ktoś sie pokusi )