Skuteczne wyszukiwanie liczby mniejszych elementów dla każdego elementu w tablicy

Utknąłem na tym problemie:

Biorąc pod uwagę tablicę $A$ z pierwszego $n$ liczby naturalne losowo permutowane, tablica $B$ jest zbudowany tak, że $B(k)$ jest liczbą elementów od $A(1)$ do $A(k-1)$ które są mniejsze niż $A(k)$ .

i) Biorąc pod uwagę $A$ czy możesz znaleźć $B$ w $O(n)$ czas?
ii) Biorąc pod uwagę $B$ czy możesz znaleźć $A$ w $O(n)$ czas?

Tutaj, $B(1) = 0$ . Konkretny przykład:

| \begin{matrix} ZA & 8 & 4 & 3) & 1 & 7 & 2) & 9 & 6 & 5 \\ b & 0 & 0 & 0 & 0 & 3) & 1 & 6 & 4 & 4 \end{matrix} |

$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\ \end{vmatrix}$

Czy ktoś może mi pomóc? Dzięki.

algorithms arrays permutations

— cholernie
źródło

Znalazłem to: obliczanie kodowania permutacji, które daje

O (n \log n)

$\mathcal O(n \log n)$ algorytmy dla tych problemów. Przynajmniej myślę, że to te same problemy.

— Realz Slaw

@Merbs, czy podana przez Ciebie wskazówka oznacza, że masz rozwiązanie?

— AJed

@AJed, oznacza to, że mam algorytm, choć trzeba

O (n^{2})

$O(n^2)$ dla prostego algorytmu bez spacji i

O (n \log n)

$O(n\log n)$ jeśli pozwolą nam miejsce. W tej chwili pochylam się, aby żadna z nich nie była możliwa

O (n)

$O(n)$ i oba są tym samym algorytmem.

— Merbs

@Merbs. Myślę, że twoja wskazówka może prowadzić do właściwej ścieżki. Mam też jedno rozwiązanie (zgodnie ze wskazówkami). Wydaje mi się, że w analizie jest pewna sztuczka

O (n)

$O(n)$ .. Myślę, że sztuczką jest wiedza, że

A

$A$ wychodzi z 1:

n

$n$ tylko.

— AJed

Ten dokument daje również

O (n \log n)

$\mathcal O(n \log n)$ algorytm. Czy jesteś pewien, że istnieje

O (n)

$\mathcal O(n)$ algorytm do tego?

— Realz Slaw

Odpowiedzi:

Naiwny algorytm ustalania $B$ od $A$ :

Dla $k=1,\dots,n$ , określ wartość $B(k)$ przez porównanie każdego z nich $A(i)$ do $A(k)$ dla $i=1,\dots,k$ i licząc tych, którzy spełniają $A(i)<A(k)$ .

Ten algorytm się porównuje $A(1)$ dla wszystkich innych ( $n-1$ czasy), $A(2)$ do $n-2$ inne itp., więc łączna liczba porównań wynosi $\frac{(n-1)(n-2)}{2}$ . Ale to nie najlepsze, co możemy zrobić. Na przykład patrząc $B(n)$ , nie musimy dokonywać żadnych porównań! $B(n)=A(n)-1$ ponieważ to pierwszy $n$ liczby naturalne i jest gwarantowane (niezależnie od permutacji), że $n-1$ będą tam niższe liczby naturalne. Co powiesz na $B(n-1)$ ? Zamiast sprawdzać $A(1)$ przez $A(n-2)$ , moglibyśmy po prostu sprawdzić $A(n)$ . To jest:

Dla $k=1, \dots,\frac{n}{2}$ , użyj powyższego algorytmu; dla $k=\frac{n}{2},\dots,n$ użyj algorytmu odwrotnego: ustal $B(k)$ ustawiając go początkowo na $A(n)-1$ a następnie odejmowanie $1$ dla każdego wpisu $A(i)$ dla $i=k+1,\dots,n$ to mniej niż $A(k)$ .

To zajmie $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ kroki, które są nadal $O(n^2)$ . Zauważ też, że przy konstruowaniu $A$ od $B$ , gdyby $B(n)=A(n)-1$ następnie $A(n)=B(n)+1$ .

Ale teraz więcej finezji. Jeśli otrzymamy dodatkowe miejsce lub sortujemy w miejscu, możemy sortować liczby, porównując je. Na przykład:

| \begin{matrix} ZA & 8 & 4 & 3) & 1 & 7 & 2) & 9 & 6 & 5 \\ S. & 9 & 8 & 7 & 4 & 3) & 2) & 1 & 6 & 5 \\ b & 0 & 0 & 0 & 0 & 3) & 1 & 6 \end{matrix} |

$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & & \\ \end{vmatrix}$

Zamiast sprawdzać je wszystkie (lub sprawdzać je w kolejności), możemy użyć wyszukiwania binarnego, aby ustalić każde z nich $B(k)$ . Jednak sortowanie wciąż wymaga czasu $O(n\log n)$ .

— Merbs
źródło

To był tylko mój pierwszy pomysł; choć zdaję sobie sprawę, że problem jest bardziej interesujący, niż początkowo go przypisywałem. I nie miałem jeszcze okazji przeczytać ustaleń Realza Slawa, więc algorytm może być wyłączony.

— Merbs

Zamiast ustalania każdego z nich $B(k)$ pojedynczo, możemy patrzeć w przyszłość i przeglądać tylko każdy numer $A$ raz ! Ale użyjemy $n$ przestrzeń:

| \begin{matrix} ZA & 1 & 2) & 3) & 4 & 5 & 6 & 7 & 8 & 9 & b \\ 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 4 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2) & 0 \\ 3) & 0 & 0 & 0 & 1 & 2) & 2) & 2) & 2) & 3) & 0 \\ 1 & 0 & 1 & 1 & 2) & 3) & 3) & 3) & 3) & 4 & 0 \\ 7 & 0 & 1 & 1 & 2) & 3) & 3) & 3) & 4 & 5 & 3) \\ 2) & 0 & 1 & 2) & 3) & 4 & 4 & 4 & 5 & 6 & 1 \\ 9 & 0 & 1 & 2) & 3) & 4 & 4 & 4 & 5 & 6 & 6 \\ 6 & 0 & 1 & 2) & 3) & 4 & 4 & 5 & 6 & 7 & 4 \\ 5 & 0 & 1 & 2) & 3) & 4 & 5 & 6 & 7 & 8 & 4 \end{matrix} |

$\begin{vmatrix} A & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & & B \\ 8 & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{0} & 1 & & 0\\ 4 & & 0 & 0 & 0 & \color{red}{0} & 1 & 1 & 1 & 1 & 2 & & 0\\ 3 & & 0 & 0 & \color{red}{0} & 1 & 2 & 2 & 2 & 2 & 3 & & 0\\ 1 & & \color{red}{0} & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & & 0\\ 7 & & 0 & 1 & 1 & 2 & 3 & 3 & \color{red}{3} & 4 & 5 & & 3\\ 2 & & 0 & \color{red}{1} & 2 & 3 & 4 & 4 & 4 & 5 & 6 & & 1\\ 9 & & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & \color{red}{6} & & 6\\ 6 & & 0 & 1 & 2 & 3 & 4 & \color{red}{4} & 5 & 6 & 7 & & 4\\ 5 & & 0 & 1 & 2 & 3 & \color{red}{4} & 5 & 6 & 7 & 8 & & 4\\ \end{vmatrix}$

Możemy zaoszczędzić jeszcze więcej czasu, nie aktualizując tych, które zostały już określone (to znaczy, nie ma sensu aktualizować $8$ po pierwszym kroku), ale w najgorszym przypadku nadal musimy dokonać aktualizacji $\frac{(n)(n+2)}{2}$ czasy

— Merbs
źródło

zarówno I, jak i II można rozwiązać za pomocą #next_greater_element, który tu wyjaśniłem . ale jest to trochę trudniejsze niż sam problem, ale przed rozwiązaniem musisz nauczyć się kolejnego większego elementu:

rozważmy, że mamy wektor dla każdego elementu $A$ Nazwij to $S_i$ dla elementu $i$ . teraz uruchom kolejny większy algorytm, zaczynając od prawej do lewej, ale z wyjątkiem elementu ustawiającego $i$ w $A$ jego następny większy indeks elementów, wciśnij $S_i$ elementy, które $i$ jest ich kolejnym większym elementem. następnie iteruj po tablicy od lewej do prawej, a następnie $B[i]=\sum_{j=0}^x (S_i[j]+1)$ gdzie $x$ to rozmiar wektora $S_i$ .i jej $\Theta(n)$ ponieważ każdy kolejny większy algorytm jest $\Theta(n)$ a także iteracja $\Theta(n)$

druga część jest również podobna, zauważając, że możemy uzyskać wartość najbardziej odpowiedniego elementu $O(1)$ EDYCJA: moje rozwiązanie jest złe, wydaje się, że nie ma żadnego $o(n)$ rozwiązanie

— Ali.Mollahoseini
źródło