Inne, zadanie nr 3109
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
darboux005 post贸w: 1 |  2015-01-24 14:26:33Dane 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