zadanie zlozonosc obliczeniowa

[kanienkahaka]

Witam. W szkole dostalismy zadanie aby pokazac, ze algorytm jednoczesnego wyszukiwania minimum i maksimum wykonuje 3/2*n-2 porownan dla n bedacego potega 2. Moglby ktos krok po kroku wytlumaczyc mi jak to pokazac?

to moja pierwsza przygoda z algorytmami nawet nie wiem czy dobrze go ulozylem i jak go napisac ale sprobuje w skrocie:

1 podziel zbior na dwa mniejsze zbiory A i Z
2 porownaj parami zbior i mniejsze elementy przydziel do zbioru A a wieksze do Z
3 znajdz najmniejszy element w zbiorze A i najwiekszy w zbiorze Z


PS. Google oblegane byly przeze mnie przez pol dnia i naprawde nie jestem w stanie zrozumiec zlozonosci obliczeniowej bez czyjejs pomocy w postaci lopatologicznego wyjasnienia

[Kokos]

3/2n-2
mam nadzieję, że to n jest w liczniku

wyszukiwanie samego maksimum wymaga n porównań. Natomiast sprawdzamy czy rozpatrywany element jest aktualnie najmniejszy tylko wtedy, gdy nie jest największy Czyli w niektórych przypadkach wiemy, że nie ma sensu porównywać na obecność minimum.

Optymistycznie będzie tylko n porównań, pesymistycznie 2n. 3/2 to średni/najczęściej występujący przypadek (dokładnie to nie wiem)

[kanienkahaka]

dzieki za pomoc ale srednio rozumiem poporstu za duzo tego mi sie zwalilo jak na jeden raz ledwo ogarniam sam sens tych algorytmow a co dopiero zlozonosci jakby ktos jeszcze mogl to jasniej wytlumaczyc to bylbym wdzieczny