... w końcu w domku.
pq - faktycznie tak jak wspomniał Dryo, ukryte pod tym linkiem rozwiązanie jest co prawda liniowym rozwiązaniem ale najwyraźniej innego problemu (chlip chlip).
Dobra, tak więc górne ograniczenie odnalezione bez żadnego wysiłku wynosi n*log(n).
W celu odnalezienia jakiegokolwiek ograniczenia dolnego posłużę się małą sztuczką - mianowicie odrobinę <font color="blue">uogólnimy </span>problem.
Powiedzmy że interesuje nas szersze zagadnienie:
Dane wejściowe:
tablica liczb tab[]
liczba całkowita k ( interesujący nas index w tablicy)
Wynik:
liczba odpowiadająca wartości tab[k] gdyby tablica została uprzednio posortowana (np. rosnąco)
Szukanie elementu środkowego jest szczególnym przypadkiem tego problemu,
mianowicie k = tab.lenght / 2
Teraz twierdzę, że dolnym ograniczeniem powyższego problemu
(jak i problemu "mediany") jest
log (n)
gdyż - jeśli złożoność ta byłaby mniejsza (powiedzmy rzędu const) to możliwe byłoby posortowanie tablicy przy złożności mniejszej od n*log(n).
Jak ? Dla każdego elementu byśmy wywołali naszą funkcję (tablica, index) i w ten sposób byśmy wyłuskali obraz posortowanej tablicy. (wszystkich elementów jest n - tyle właśnie razy należałoby wywołać tą funkcję)
W takim razie mamy:
górne ograniczenie - n*log(n)
dolne ograniczenie - log(n)
Możemy mówić więc o istnieniu pewnej luki algorytmicznej - wszak "widełki" - czyli różnica pomiędzy aktualnie najlepszym znanym rozwiązaniem a udowodnionym dolnym progiem złożoności obliczeniowej, jest dość znaczna.
Osobiście (ale to tylko moja opinia) sądzę, że n*log(n) jest najlepszym rozwiązaniem i teraz raczej należałoby wykazać że dolne ograniczenie złożoności obliczeniowej jest w rzeczywistości wyższe od log(n).
Na koniec zwracam uwagę na dwa ciekawe aspekty omawianego problemu:
- Nie znaleźliśmy (według mnie nie znajdziemy) rozwiązania liniowego, natomiast zagadnienie odwrotne - czyli:
mamy tablicę tab[] oraz liczbę x, należy sprawdzić czy liczba x leżałaby pośrodku tab[] gdyby ta była posortowana -
ten problem ma rozwiązanie liniowe (zliczanie liczby elementów większych od x i liczby elementów mniejszych od x - całość wykonana dla każdego elementu tablicy czyli złożoność rzędu n)
- Dość banalny algorytm sortowania klasy n2 - sortowanie bąbelkowe, ma pewną ciekawą właściwość...
mianowicie wykonujemy n-krotne przemieszczanie n-elementów i po każdym zakończonym kroku tablica jest na pewnym odcinku końca tablicy posortowana ( w szczególności oznacza to, że po pierwszym przemieszczaniu na samym końcu tablicy znajdzie się element największy (o ile sortujemy rosnąco) ).
Z tego wynika wprost, że problem wyszukiwania elementu maksymalnego ma złożność liniową.
Natomiast, gdybyśmy chcieli odnaleźć (za pomocą tej metody) element środkowy, wymagałoby to n/2 krotnego przemieszczania n-elementów czyli złożoność:
1/2*n2
koniec
1/2*n2 to w rzeczywistości złożoność kwadratowa (aczkolwiek ten przyjemny współczynik 1/2 nie pozostaje całkowicie bez znaczenia - tak czy inaczej nie zmienia on klasy algorytmu)
Dlatego nadal najszybsze - n*log(n) jest posortowanie tablicy np. QuickSortem a następnie zwyczajne odczytanie środkowego elementu ... i chyba nie powinno dziwić to, że odwołujemy się do sortowania - ostatecznie przecież to sortowanie jest wpisane w treść naszego zadania.
Pozdrawiam
P.S. medal dla tego kto odnajdzie lepszy algorytm (w sensie złożoności) albo wykaże, że dolne ograniczenie jest wyższe od log(n) ...
P.P.S - kurcze, to dopiero jest mój 203 post - hi hi