Inne, zadanie nr 3109

Autor	Zadanie / Rozwiązanie
darboux005 postów: 1	2015-01-24 14:26:33 Dane są dwa ciągi liczb całkowitych, A i B, długości n każdy, przy czym n›1. Zakładamy, że dla każdej liczby całkowitej x, x należy do co najwyżej jednego z tych ciągów. Opracować algorytm wyznaczania mediany tych ciągów w czasie Θ(lgn). Odpowiedź dokładnie uzasadnić. Zadanie co prawda nie z matematyki, ale studiuje na matematyce i Algorytmy i Struktury Danych również mamy. Będę wdzięczna za poprawną odpowiedź

tumor postów: 8070	2016-06-27 08:49:56 Przede wszystkim ciągi są posortowane, bo dla bajzlu nie znajdziemy mediany bez przeszukania wszystkich elementów. Nazwijmy te ciągi L i P. Jeśli ilość elementów w tych ciągach jest nieparzysta, to $x_l, x_p$ niech oznaczają ich środkowe elementy. Jeśli parzysta, to w ciągu L niech $x_l$ będzie "lewym" z dwóch środkowych, tzn $x_l$ ma indeks $\frac{n}{2}$ w L, natomiast $x_p$ niech będzie "prawym", czyli ma w P indeks $\frac{n}{2}+1$ (zakładam numerację elementów ciągów od 1, łatwo sobie przerobić na numerację od 0). Jako że elementy się w ciągach nie powtarzają, $x_l \neq x_p$. Jeśli $x_l<x_p$ to kasujemy wszystkie elementy z L o indeksach mniejszych niż l, wszystkie elementy z P o indeksach większych niż P. Jeśli nierówność jest w drugą stronę, to i kasowanie. Dla skróconych ciągów wykonujemy powyższą procedurę raz jeszcze, aż po kolejnym kroku ciągi L,P są dwuelementowe, wtedy z czterech elementów medianę liczymy po prostu. Załóżmy, że w k-tym kroku wyszło $x_l<x_p$. Wówczas mediana znajduje się w przedziale $[x_l,x_p]$, bowiem tyle samo elementów jest większych od $x_p$, ile jest mniejszych od $x_l$. Dlatego też możemy te skrajne elementy odrzucić. Dlatego też w jednym z ciągów w przypadku parzystości bierzemy element "lewy" a w drugim "prawy", żeby z każdego końca odrzucić tyle samo elementów. W każdym kroku dla ciągów o długości $k$ każdy (czyli $2k$ razem) odrzucamy co najmniej $k-2$ elementów niebędących medianą, co gwarantuje nam złożoność $\Theta (lg(n))$.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj