[Algorytmy] Modyfikacja algorytmy "mediana median"

silvaran · Post autor: **silvaran** » 12 paź 2012, o 22:34

Algorytm znany jako magiczne piątki lub mediana median (idea oparta na pomyśle szybkiego sortowania) wyszukuje k-tą co do wartości wielkość z \(\displaystyle{ n}\)-elementowego nieuporządkowanego wektora. Czy ma ktoś pomysł jak zmodyfikować ten algorytm, aby jego złożoność czasowa pozostała bez zmian i znajdował on największą wartość spełniającą warunek, że \(\displaystyle{ y_k\geq k}\) przy założeniu, że \(\displaystyle{ y}\) to posortowany malejąco wektor \(\displaystyle{ x}\).

Kartezjusz · Post autor: **Kartezjusz** » 13 paź 2012, o 07:54

Podaj jakiś przykład ,bo nie kumam o co Ci chodzi.

silvaran · Post autor: **silvaran** » 13 paź 2012, o 09:50

Ale przykład czego?
Chodzi o to, żeby wyznaczyć indeks h (albo indeks Hirscha) bez potrzeby sortowania danych.

Kartezjusz · Post autor: **Kartezjusz** » 13 paź 2012, o 14:25

Produkujesz wektor cytowań prac naukowych i i produkujesz pętlę. Założyłeś,że wektor posortowany jest malejąco.
\(\displaystyle{ i=0}\)
while \(\displaystyle{ y_{i}>h}\) indeks Hirscha to chyba ta wartość jest stała dla danego naukowca.

silvaran · Post autor: **silvaran** » 13 paź 2012, o 22:50

No właśnie chcę uniknąć sortowania ! Zrobić to tak, żeby złożoność czasowa była \(\displaystyle{ O(n)}\) wykorzystując algorytm magicznych piątek, który właśnie działa w takim czasie.

Kartezjusz · Post autor: **Kartezjusz** » 13 paź 2012, o 22:57

Czy to możliwe. Bo nie tylko musisz wyznaczyć k-ty element, ale i porównać go z indeksem

silvaran · Post autor: **silvaran** » 13 paź 2012, o 22:59

Właśnie też sie zastanawiam czy to jest wykonalne...

Zordon · Post autor: **Zordon** » 14 paź 2012, o 00:17

Da się to liniowo, ale będzie brzydkie. Robimy to rekurencyjnie, pierwszy krok to obliczenie mediany w O(n), następnie odpalamy się w lewej lub prawej połówce zależnie od tego czy \(\displaystyle{ mediana>n/2}\). To ma złożoność \(\displaystyle{ n+n/2+n/4+...=O(2n)}\)

silvaran · Post autor: **silvaran** » 14 paź 2012, o 11:16

Jeśli \(\displaystyle{ med>n/2}\) to odpalamy się w prawej chyba, tak? Czyli w tym zbiorze \(\displaystyle{ A_>}\) znowu szukamy mediany