English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: liniowe rozwiązanie do kurierów
Nie wiem, jak miałoby działać, ale słyszałem plotki że takie istnieje. Ktokolwiek widział, ktokolwiek wie...
Chyba dałeś złego linka, bo psorek pytał o liniowe rozwiązanie.
na końcu jest opisywane
Polecam wtyczkę TeX The World for Chromium lub jakiś ekwiwalent pod inne przeglądarki.
Niestety, ale jakby na to nie patrzeć, to to rozwiązanie nie jest liniowe. Jeżeli chcemy uzyskać na [; m ;] zapytaniach prawdopodobieństwo równe [; a ;] to musimy na każdym zapytaniu wykonać [; \log_2 \left( \frac{1}{1 - a^{\frac{1}{m}}} \right) ;] sprawdzeń. Jest to [; O(log(m)) ;], gdyż [; \lim_{m \to \infty} \frac{\frac{1}{1 - a^{\frac{1}{m}}}}{m} = -\frac{1}{ln(a)} ;]
Zatem złożoność podanego rozwiązania to [; O(n + m \log m) ;]
Niestety, ale jakby na to nie patrzeć, to to rozwiązanie nie jest liniowe. Jeżeli chcemy uzyskać na [; m ;] zapytaniach prawdopodobieństwo równe [; a ;] to musimy na każdym zapytaniu wykonać [; \log_2 \left( \frac{1}{1 - a^{\frac{1}{m}}} \right) ;] sprawdzeń. Jest to [; O(log(m)) ;], gdyż [; \lim_{m \to \infty} \frac{\frac{1}{1 - a^{\frac{1}{m}}}}{m} = -\frac{1}{ln(a)} ;]
Zatem złożoność podanego rozwiązania to [; O(n + m \log m) ;]
Czy to, co teraz wymyśliłem, jest na pewno dobre (i liniowe)? Aż sam się nieco zdziwiłem...
Niech dla dowolnego skończonego zbioru X zbiór [; L_d(X) ;] oznacza zbiór tych elementów, które występują w X co najmniej [; d|X| ;] razy - przy czym d jest pewną stałą. Powiedzmy też sobie, że ktoś miły wyznaczył nam [; L_d ;] dla każdego przedziału bazowego (przedziałów tych jest mniej niż [; 2n ;], więc suma rozmiarów wszystkich zbiorów nie przekroczy [; \inline \frac{2n}{d} = O(n) ;]).
Spróbujemy dla pewnego przedziału o szerokości [; l ;] wyznaczyć nie więcej niż C potencjalnych liderów - gdzie C jest pewną stałą. Ustalmy [; 2^k ;] jako rozmiar wykorzystywanego przez nas przedziału bazowego. Weźmy więc te przedziały bazowe, które mieszczą się w zadanym przedziale. Zauważmy, że zarówno od lewej, jak i prawej strony zostają niepokryte podciągi liczb o długości mniejszej niż [; 2^k ;]. Pokrywamy więc więcej niż [; l-2^{k+1} ;] liczb. Oczywiście te operacje można wykonać w czasie [; \inline O(\frac{l}{2^k}) ;] - czyli stałym przy odpowiednio dużym k.
Powiedzmy teraz, że dowolny wybrany przez nas element x należący do całego ciągu nie należy do żadnego zbioru [; L_d ;] dla żadnego z naszych przedziałów bazowych. Wtedy x nie może wystąpić w więcej niż [; dl ;] elementach należących do pokrytych liczb oraz [; 2^{k+1} ;] elementach należących do niepokrytych liczb (bo takich liczb jest nie więcej niż tyle). Tak więc x występuje w badanym przedziale w nie więcej niż [; dl+2^{k+1} ;] miejscach. Ta wartość ma być nie większa niż [; l/2 ;], czyli równoważnie [; \inline 2^{k+1} \leq l(\frac12-d). ;] Biorąc [; \inline d=\frac13 ;] oraz upraszczając, otrzymujemy [; \inline 2^k \leq \frac1{12}l. ;] Bierzemy więc długość przedziałów bazowych [; \inline 2^k \in \left(\frac1{24}l, \frac1{12}l\right> ;] (jeśli [; l < 12 ;], to po prostu bierzemy wszystkie liczby należące do przedziału jako kandydatów). Wtedy oczywiście jedynymi możliwymi wyborami na kandydata są elementy należące do [; L_d. ;] Nietrudno więc zauważyć, że skoro [; \inline \frac{l}{2^k} < 24, ;] to pokryjemy przedział mniej niż 24 przedziałami bazowymi, a przy naszym wyborze d oznacza to, że możliwych kandydatów jest mniej niż [; 24 \cdot 2=48 ;] (bo żaden przedział nie może mieć więcej niż dwóch 1/3-liderów).
Pozostał jedynie problem wyznaczania [; L_{1/3}(X) ;] dla X - wszystkich przedziałów bazowych ;). Tutaj jednak obserwacja jest podobna do tej, jak we wzorcówce - gdy weźmiemy trzy różne elementy należące do X i je wywalimy, to każdy element, który dotychczas występował w co najmniej 1/3 elementów, wciąż będzie spełniał ten warunek. Dlatego też liczenie tych zbiorów jest bardzo podobne do firmówki. Inicjujemy przedziały o szerokości 1, a następnie idziemy w górę drzewa przedziałowego zbudowanego na przedziałach bazowych. W każdym węźle ostatecznie trzymać będziemy kandydatów na 1/3-liderów i policzoną liczbę wystąpień "ponad" 1/3. Jeśli w trakcie tworzenia przedziału bazowego o szerokości [; 2^k ;] w dwóch łączonych przedziałach o szerokości [; 2^{k-1} ;] pojawia się co najmniej 3 kandydatów na 1/3-lidera, to "redukujemy" ich dokładnie tak, jak we wzorcówce. Nietrudno zauważyć, że ten preprocessing zajmuje czas [; O(n) ;]. Każdy z badanych przedziałów początkowo przetwarzamy w czasie [; O(1) ;]. Wytwarzamy łącznie [; O(m) ;] kandydatów na liderów, a ich przetworzenie algorytmem ze wzorcówki zajmie czas równy [; O(n+m) ;] (sortowanie zdarzeń wykonujemy poprzez sortowanie przez zliczanie). Tak więc wygląda na to, że algorytm jest liniowy - z duuużą stałą, ale jednak liniowy ;)
Niech dla dowolnego skończonego zbioru X zbiór [; L_d(X) ;] oznacza zbiór tych elementów, które występują w X co najmniej [; d|X| ;] razy - przy czym d jest pewną stałą. Powiedzmy też sobie, że ktoś miły wyznaczył nam [; L_d ;] dla każdego przedziału bazowego (przedziałów tych jest mniej niż [; 2n ;], więc suma rozmiarów wszystkich zbiorów nie przekroczy [; \inline \frac{2n}{d} = O(n) ;]).
Spróbujemy dla pewnego przedziału o szerokości [; l ;] wyznaczyć nie więcej niż C potencjalnych liderów - gdzie C jest pewną stałą. Ustalmy [; 2^k ;] jako rozmiar wykorzystywanego przez nas przedziału bazowego. Weźmy więc te przedziały bazowe, które mieszczą się w zadanym przedziale. Zauważmy, że zarówno od lewej, jak i prawej strony zostają niepokryte podciągi liczb o długości mniejszej niż [; 2^k ;]. Pokrywamy więc więcej niż [; l-2^{k+1} ;] liczb. Oczywiście te operacje można wykonać w czasie [; \inline O(\frac{l}{2^k}) ;] - czyli stałym przy odpowiednio dużym k.
Powiedzmy teraz, że dowolny wybrany przez nas element x należący do całego ciągu nie należy do żadnego zbioru [; L_d ;] dla żadnego z naszych przedziałów bazowych. Wtedy x nie może wystąpić w więcej niż [; dl ;] elementach należących do pokrytych liczb oraz [; 2^{k+1} ;] elementach należących do niepokrytych liczb (bo takich liczb jest nie więcej niż tyle). Tak więc x występuje w badanym przedziale w nie więcej niż [; dl+2^{k+1} ;] miejscach. Ta wartość ma być nie większa niż [; l/2 ;], czyli równoważnie [; \inline 2^{k+1} \leq l(\frac12-d). ;] Biorąc [; \inline d=\frac13 ;] oraz upraszczając, otrzymujemy [; \inline 2^k \leq \frac1{12}l. ;] Bierzemy więc długość przedziałów bazowych [; \inline 2^k \in \left(\frac1{24}l, \frac1{12}l\right> ;] (jeśli [; l < 12 ;], to po prostu bierzemy wszystkie liczby należące do przedziału jako kandydatów). Wtedy oczywiście jedynymi możliwymi wyborami na kandydata są elementy należące do [; L_d. ;] Nietrudno więc zauważyć, że skoro [; \inline \frac{l}{2^k} < 24, ;] to pokryjemy przedział mniej niż 24 przedziałami bazowymi, a przy naszym wyborze d oznacza to, że możliwych kandydatów jest mniej niż [; 24 \cdot 2=48 ;] (bo żaden przedział nie może mieć więcej niż dwóch 1/3-liderów).
Pozostał jedynie problem wyznaczania [; L_{1/3}(X) ;] dla X - wszystkich przedziałów bazowych ;). Tutaj jednak obserwacja jest podobna do tej, jak we wzorcówce - gdy weźmiemy trzy różne elementy należące do X i je wywalimy, to każdy element, który dotychczas występował w co najmniej 1/3 elementów, wciąż będzie spełniał ten warunek. Dlatego też liczenie tych zbiorów jest bardzo podobne do firmówki. Inicjujemy przedziały o szerokości 1, a następnie idziemy w górę drzewa przedziałowego zbudowanego na przedziałach bazowych. W każdym węźle ostatecznie trzymać będziemy kandydatów na 1/3-liderów i policzoną liczbę wystąpień "ponad" 1/3. Jeśli w trakcie tworzenia przedziału bazowego o szerokości [; 2^k ;] w dwóch łączonych przedziałach o szerokości [; 2^{k-1} ;] pojawia się co najmniej 3 kandydatów na 1/3-lidera, to "redukujemy" ich dokładnie tak, jak we wzorcówce. Nietrudno zauważyć, że ten preprocessing zajmuje czas [; O(n) ;]. Każdy z badanych przedziałów początkowo przetwarzamy w czasie [; O(1) ;]. Wytwarzamy łącznie [; O(m) ;] kandydatów na liderów, a ich przetworzenie algorytmem ze wzorcówki zajmie czas równy [; O(n+m) ;] (sortowanie zdarzeń wykonujemy poprzez sortowanie przez zliczanie). Tak więc wygląda na to, że algorytm jest liniowy - z duuużą stałą, ale jednak liniowy ;)
Wiadomość została ukryta przez administratora.
Wiadomość została ukryta przez administratora.