Liczenie par inwersji


14

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 ( i , j ) takie, że a [ i ] > a [ j ] i i < j .za[1n](ja,jot)za[ja]>za[jot]ja<jot

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(nlogn)

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.Θ(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 ) )?O(nlogn)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)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.


3
Chan i Pătraşcu podają algorytm czasowy , ale o ile wiem po przejrzeniu papieru, potrzebują przestrzeni Ω ( n ) . o(nlogn)Ω(n)
Raphael

2
Ponadto Ajtai i in. udowodnić, że dowolny (dokładny) algorytm strumieniowania czasu potrzebuje przestrzeni Ω ( n ) . Wydaje się jednak, że istnieją przybliżenia pasujące do twoich kryteriów. O(n)Ω(n)
Raphael

1
@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)

Odpowiedzi:


3

Oto odpowiedź Raphaela:

o(nlogn)Ω(n)O(n)Ω(n)


Dzięki za odpowiedź. Daję mu jednak trochę więcej czasu. Wydaje się, że ruch rośnie.
Aryabhata,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.