Liczenie par inwersji

Klasyczne zastosowanie dzielenia i podbijania polega na rozwiązaniu następującego problemu:

Biorąc pod uwagę tablicę różnych, porównywalnych elementów, policz liczbę par inwersji w tablicy: pary takie, że i . $a[1\dots n]$ $(i,j)$ $a[i] \gt a[j]$ $i \lt j$

Jednym z podejść jest wykonanie sortowania scalającego, ale także zliczanie liczby par inwersji w pod-problemach. Podczas kroku scalania zliczamy liczbę par inwersji obejmujących (dwa) podproblemy i dodajemy do podproblemów.

Chociaż jest to dobre i daje algorytm czasowy , to miesza tablicę. $O(n\log n)$

Jeśli mamy dodatkowe ograniczenie polegające na tym, że tablica jest tylko do odczytu, możemy wykonać kopię i poradzić sobie z kopią lub użyć dodatkowej struktury danych, takiej jak drzewo binarne zrównoważone statystyki zamówień, aby wykonać zliczanie, z których oba używają spacja. $\Theta(n)$

Bieżącym pytaniem jest próba ulepszenia przestrzeni, bez wpływu na czas działania. to znaczy

Czy istnieje algorytm czasowy do zliczania par par inwersji, który działa na tablicy tylko do odczytu i wykorzystuje przestrzeń subliniową (tj. )? $O(n\log n)$ $o(n)$

Załóżmy, że model RAM o jednolitym koszcie i że elementy zajmują miejsce a porównanie między nimi wynosi . $O(1)$ $O(1)$

Odniesienie się sprawdzi, ale wyjaśnienie będzie lepsze :-)

Próbowałem przeszukać sieć, ale nie znalazłem na to żadnej pozytywnej / negatywnej odpowiedzi. Przypuszczam, że to tylko ciekawostka.

algorithms reference-request arrays

— Aryabhata
źródło

Chan i Pătraşcu podają algorytm czasowy

, ale o ile wiem po przejrzeniu papieru, potrzebują przestrzeni

o (n \log n)

$o(n \log n)$

Ω (n)

$\Omega(n)$

— Raphael

Ponadto Ajtai i in. udowodnić, że dowolny (dokładny) algorytm strumieniowania czasu

potrzebuje przestrzeni

. Wydaje się jednak, że istnieją przybliżenia pasujące do twoich kryteriów.

O (n)

$O(n)$

Ω (n)

$\Omega(n)$

— Raphael

@Raphael: Dzięki! Jeśli nie otrzymamy żadnej odpowiedzi, Twój komentarz byłby jak dotąd najlepszą odpowiedzią.

— Aryabhata

BTW Jestem trochę zdezorientowany tą dolną granicą Ajtai i in. Twierdzenie 8 mówi „dowolny algorytm”, ale dolna granica wydaje mi się przeciwna algorytmom strumieniowania dokładnego jednoprzebiegowego, bardzo ograniczonemu modelowi

— Sasho Nikolov

O (n)

$O(n)$

Oto odpowiedź Raphaela:

$o(n\log n)$ $\Omega(n)$ $O(n)$ $\Omega(n)$

— Yuval Filmus
źródło

Dzięki za odpowiedź. Daję mu jednak trochę więcej czasu. Wydaje się, że ruch rośnie.

— Aryabhata,