[Algorytmy] rozdzielenie tablicy na dwie względem mediany

gmore
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 6 paź 2017, o 21:36
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy

[Algorytmy] rozdzielenie tablicy na dwie względem mediany

Post autor: gmore » 4 lis 2017, o 21:01

Mamy tablicę parzystej długości - \(\displaystyle{ A[2n]}\) - wypełnioną liczbami całkowitymi. Chcemy ją tak przestawić, by zachodziło \(\displaystyle{ A[k] \le A[j]}\) dla dowolnych \(\displaystyle{ k\le n ;j>n}\) (używam tu konwencji, że tablicę numerujemy poczynając od jedynki). Jak to zrobić w \(\displaystyle{ O(n)}\)? Wiadomo, że dla \(\displaystyle{ O(n\log (n))}\) wystarczy sobie posortować.
Ostatnio zmieniony 4 lis 2017, o 21:54 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Punkt 2.7 instrukcji LaTeX-a. Funkcje matematyczne należy zapisywać: sinus - \sin, logarytm - \log, logarytm naturalny - \ln itd. Poprawa wiadomości: \le.

Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

Re: [Algorytmy] rozdzielenie tablicy na dwie względem median

Post autor: Afish » 4 lis 2017, o 22:12

Algorytm magicznych piątek.

ODPOWIEDZ