[Algorytmy] Modyfikacja algorytmy "mediana median"
-
- Użytkownik
- Posty: 1300
- Rejestracja: 6 sty 2009, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice/Warszawa
- Podziękował: 60 razy
- Pomógł: 123 razy
[Algorytmy] Modyfikacja algorytmy "mediana median"
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}\).
Ostatnio zmieniony 13 paź 2012, o 10:56 przez Afish, łącznie zmieniany 1 raz.
Powód: Taguj tematy.
Powód: Taguj tematy.
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
-
- Użytkownik
- Posty: 1300
- Rejestracja: 6 sty 2009, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice/Warszawa
- Podziękował: 60 razy
- Pomógł: 123 razy
Modyfikacja algorytmy "mediana median"
Ale przykład czego?
Chodzi o to, żeby wyznaczyć indeks h (albo indeks Hirscha) bez potrzeby sortowania danych.
Chodzi o to, żeby wyznaczyć indeks h (albo indeks Hirscha) bez potrzeby sortowania danych.
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
[Algorytmy] Modyfikacja algorytmy "mediana median"
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.
\(\displaystyle{ i=0}\)
while \(\displaystyle{ y_{i}>h}\) indeks Hirscha to chyba ta wartość jest stała dla danego naukowca.
-
- Użytkownik
- Posty: 1300
- Rejestracja: 6 sty 2009, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice/Warszawa
- Podziękował: 60 razy
- Pomógł: 123 razy
[Algorytmy] Modyfikacja algorytmy "mediana median"
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.
-
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
[Algorytmy] Modyfikacja algorytmy "mediana median"
Czy to możliwe. Bo nie tylko musisz wyznaczyć k-ty element, ale i porównać go z indeksem
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
[Algorytmy] Modyfikacja algorytmy "mediana median"
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)}\)
-
- Użytkownik
- Posty: 1300
- Rejestracja: 6 sty 2009, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice/Warszawa
- Podziękował: 60 razy
- Pomógł: 123 razy
[Algorytmy] Modyfikacja algorytmy "mediana median"
Jeśli \(\displaystyle{ med>n/2}\) to odpalamy się w prawej chyba, tak? Czyli w tym zbiorze \(\displaystyle{ A_>}\) znowu szukamy mediany