[Algorytmika] Mediana?

0

Ma do zrobienia programik, w którym jedno z zadań to wyszukiwanie elementu w nieposortowanej tablicy, który po posortowaniu znalazłby się w środku tablicy (liczba elementów jest nieparzysta).
Najprostrzy sposób to oczywiście przeszukiwanie po kolei kolejnych najmniejszych n/2 wartości. Ale złożoność takiego algorytmu to 0.5*N2
W zadaniu nie istotna jest złożoność i napisaniu takiego programu to bułka z masłem (zwłaszcza, że liczba elementów tej tablicy jest znikoma). Ale nie byłbym sobą, gdybym sobie nie komplikował życia. Poszukuję wydajnego algorytmu (załóżmy, że liczbę elementów liczymy w milionach), który wyszukiwałby element środkowy w czasie liniowym O(N).

  1. Czy jest możliwe zrobienie takigo algorytmu? (tak na oko wydaje się, że tak)
  2. Jak coś takiego zrobić? (różne ciekawe kombinacje robiłem, z wynikami w większości przypadków poprawnymi, jednak zdarzały się specyficzne dane, dla których algorytm zawodził).
    Czekam na sugestie.
    Aaa. Nie chcę gotowego kodu, a jedynie opis algorytmu lub jakieś wskazówki.
0

To może zrób posortowaną tablicę ze wskaźnikami na elemetny tablicy?? Będziesz miał nieposortowaną tablicę, z której możesz wyciągnąc nty element...

0

czas dwokrotnie rosnie, bo najpierw sortujesz a potem szukasz
i jakie są elementy w tej tablicy? liczby znaki? liczby zmienno przecinkowe, to tez ważne bo do danego typu są różne metody szukania

0

Liczby całkowite. Można nawet przyjąć, że dodatnie.
Vogel o to chodzi, żeby nie sortować, nie tworzyć drugiej tablicy.
Ja już kombinowałem różne modyfikacje twierdzenia o wartości średniej, ale to nie bardzo wychodziło.
Może jeszcze przykład dam, żeby nie było wątpliwości:
Tablica:
1 3 5 2 8 4 9
Po posortowaniu wyglądałaby tak:
1 2 3 4 5 8 9
Czyli elementem środkowym miałaby być 4.
I nie zmieniajc kolejności elementów w tablicy (i nie tworząc żadnej pomocniczej) znaleźć tą 4. Można jakieś pomocnicze liczniki używać.
Najprostszy sposób to poszukiwanie kolejnych najmniejszych (lub największych) liczb. Ale przy N elementach mamy złożoność 0,5*N2 Niby niewiele. Ale jak wspominałem lubię kombinować :

0

a czy nie zastosować jakiś juz sprawdzonych metod wyszukujących np
Algorytm RK (Rabin-Karp)

http://aragorn.pb.bialystok.pl/~mirkowsk/asd/wyklady/W05_II.html

0

RK kompletnie się do tego nie nadaje :) To nie jest wyszukiwanie wzorca tylko pojedynczego elementu.
Coś czuję, że pozostanie mi implementacja najprostszego pomysłu.
Ale temat zostawiam otwarty, bo interesuje mnie rozwiązanie (albo chociaż dowód, że takie istnieje lub nie). Może jak się pojawi Kapustka to coś wymyśli.
I chyba pójdzie to do Gorących tematów.

0

Bardzom ciekaw odpowiedzi Kapustki i innych mądrych osób. Trochę myślałem - bez skutku - no ale to niewiele znaczy ;).

Może jednak najszybciej posortowac i odczytac srodkowy element. Cytat ze Skysha: "heapsort dziala nln(n) dla najgorszych danych. " Wiec chyba szybciej niz 0.5n^2

0

Kup sobie Biblię programistów (Wstęp do algorytmiki). Tak mi śmiga, że to było tam...

0

hmm co do roźnych metod wyszukiwania to ja kiedyś połączyłęm metode QuickSort z szukaniem elementow,
fakt wymagało to tego aby elementy były poukładane
i trzeba tylko wykorzystać wydajne algorytmy i wziąc pod uwage fakt jak bardzo spowolnią aby dostosować je do naszego pomysłu, jęśli zysk bedzie duzy to sie opłaca

0

:-D Nie czytacie uważnie. Założenia zadania są takie, aby nie sortować
Co do działania HeapSort to wiem o jego działaniu ze złożonością ok. 2nln(n). QuickSort dla średnich danych ma już natomiast wydajność ok. 1,4nln(n) :) (dla najgorszych n2).
Ale tu wcale nie chodzi o sortowanie. Książek jest ci u mnie dostatnek i znajomości podstawowych sposobów sortowania też.

0

Ja myslalem jakos tak:
dane sa w array x

najpiwerw me=x[1]

potem pobierac kolejne x i wyznaczac mediane w zaleznosci od tego, czy x[n] jest wieksze czy mniejsze od aktualnego me. Ale to wymaga stworzenia dwoch rosnacych list 'powyzej me' i 'ponizej me' ktore w dodatku musza byc sortowane. Zeby bylo wiadomo co ma sie 'stawac'mediana. A przynajmniej kazdy kolejny x[n] musi byc wstawiany do odpowiedniej listy na wlasciwe miejsce. no i jak sie me zmienia to bedzie tez potzrebne przekladanie z listy do listy. Moze to sie da uproscic w ten sposob, zeby nie analizowac x'ow znajdujacych sie na listach tak daleko od aktualnej mediany, ze na pewno juz nie beda ostaeczna mediana...

czuje, ze to sa jakies bardzo metne rozwazania przed polnoca. [wstyd]
dobranoc

0

:-D Nie czytacie uważnie. Założenia zadania są takie, aby nie sortować

<font color="darkblue">Ale czemu nie sortować jak byłoby to szybsze i prost<font color="red">sz</span>e [stuk] </span>

Najlepsze są najprost<font color="red">sz</span>e rozwiązania... :d

0

<font color="darkblue">Ale czemu nie sortować jak byłoby to szybsze i prost<font color="red">sz</span>e [stuk] </span>
Bo na tym właśnie zadanie polega. To nie chodzi o to co ja chcę, tylko czego się ode mnie wymaga.

0

Hej hej.
... prawdopodobnie nie zdołam napisać wszystkiego co bym chciał, gdyż w piszę na przerwie ...

Mamy daną tablicę i szukamy elementu środkowego - jak to zrobić najszybciej ? (Celowo pomijam kryterium "nie wolno sortować")

Oczywiście, tak jak większość z nas, rozpisałem sobie kilka przypadków na kartce papieru i zastanawiałem się jak rozwiązać ten problem ... od razu powiem - nie znam rozwiązania.

Ciekawym pytaniem jest - "jaką możemy osiągnąć najlepszą złożoność obliczeniową ?" ponizej zamieszczam krótką analizę dolnego i górnego ograniczenia.

Pierwszym rozwiązaniem jakie przychodzi nam do głowy jest:
"posortujemy całą tablicę i odczytamy środkowy element".

Najszybsze algorytmy sortowania mają złożoność obliczeniową rzędu n*log(n). Więc po uwzglęnieniu faktu, że odczytanie elementu spod zadanego indeksu jest dokonywane w czasie stałym szybko otrzymujemy:

górne ograniczenie = n*log(n)
{ nie jest źle, to już prawie liniowa złożoność }

... w tej chwili kończy mi się przerwa ...

0

To troszkę nie najciekawsze jest tam podane rozwiązanie.
Nie licząc tego, że problem dotyczył 3 liczb, to przedstawiony tam algorytm jest błędny! Z tego, co zrozumiałem z kodu, to analizuje on częstotliwość występowania liczb, a następnie sprawdza, aż sum ich wyniesie połowę wartości. To nie jest prawidłowe rozwiązanie. Może sformułowanie mediana nie było z mojej strony najwłaściwsze.
Ale skoro twierdzą tam, że istnieje rozwiązanie o czasie wielomianowym, to już jest to dla mnie dużo informacji.

Jakby co to dziś już zaliczyłem te zadanko z mediany :) (ale to nie o to chodziło). Jeszcze będę szukał na wspomnianych tam stronach. W każdym razie problem dalej pozostaje dla mnie ciekawy.

0

... 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:

  1. 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)

  1. 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

0

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) ...

Cóż. Nie wykaże. Ale napomnę jedynie, że moim zdaniem dolne ograniczenie to co najmniej O(n), ponieważ wydaj mi się, że musimy odczytać każdy element co najmniej raz. Musimy znać przynajmniej stosunek tej liczby do pozostałych. Na wzór problemu odwrotnego - sprawdzania czy jest w środku.

P.P.S - kurcze, to dopiero jest mój 203 post - hi hi

203 z pośród 203 bardzo pomocnych postów. Czyli najlepszy możliwy stosunek :)
A tak w ogóle nie przejmuj się. Już niedługo (miejmy nadzieję) zniknie liczba postów (przynajmniej mam nadzieję, że moich z oczu innych i innych z moich oczu).

W każdym razie dzięki wszystkim, za próbę rozwiązania.
Mam nadzieję, że jednak istnieje takie rozwiązanie o złożoności

0

a metoda magicznych piątek?

0

A datę waszmość sprawdził?

0

Nie sprawdził, ale za to jedyny poprawnie odpowiedział na oryginalny problem ;)
Algorytm magicznych piątek znajduje medianę w O(n).

0

BTW: jakby ktoś kiedyś szukał, to co z tego, że odpowiedź się pojawiła po takim długim czasie. Ważne, że w końcu jest. To jest czasem frustrujące na forach: szukasz odpowiedzi na pytanie, znajdujesz na forum dokładnie Twoje pytanie, później 3 strony wątku ale brak satysfakcjonującej Cię odpowiedzi.

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