Jak wybrać wszystkie elementy z listy, które są nieczynne?

Question

To pytanie powstało z dyskusji w komentarzach this answer.

Po pierwsze, powiedzmy, że trudno jest określić, co jest poza zamówieniem. Biorąc pod uwagę przykład Pavela Shveda, na liście [1,5,10,2,3,4,5,6,7,8,9,10,11] możemy "wyraźnie" zobaczyć, że 5 i 10 (wskaźniki 1) i 2) są niesprawne. Ale naiwny algorytm, który po prostu sprawdza jakąś sortowaną listę niezmienników, nie wskazywałby na to.

• sprawdzenie a[i-1]<=a[i] for all 0<i<=N dałoby element o indeksie 3 (czyli 2);

• sprawdzenie a[j]<=a[i] for all 0<=i<=N and 0<=j<=i dałoby wszystkie elementy w indeksach od 3 do 12;

Moje pytanie brzmi: czy można wymyślić algorytm rozwiązania tego problemu, który daje "poprawną odpowiedź" (tj. Wskaźniki 1 i 2)? Jeśli tak, to w jakim czasie i przy użyciu złożonej pamięci będzie działać?

Answer 1

Prawdopodobnie najlepszym rozwiązaniem byłoby najpierw znaleźć longest increasing subsequence, a następnie uznać wszystkie elementy, które nie są częścią tej sekwencji, za niesprawne. Algorytm dostarczony na połączonej stronie działa w czasie O(n log n) i korzysta z przestrzeni O(n) (oprócz samej listy).

Takie podejście na pewno wydajność poprawną odpowiedź za przykład przypadku, ponieważ najdłuższy zwiększenie podciąg będzie od 1 do 11 sekwencji nie licząc dodatkowych 5 i 10.

Answer 2

Jak algorytm wiedzieć, które elementy, które rozważyć nieczynność?

Jeśli reguła jest "lista [i + 1] powinna zawsze być lista [i] + 1", to oczywiście łatwo byłoby po prostu zapamiętać, że po 1, następny element powinien być 2, wybierz te pomiędzy i tak dalej. Potrzebna jest jednak precyzyjna reguła dla algorytmu, który określi, które elementy należy uznać za "nieczynne".

Answer 3

Jak powiedział Dav, longest increasing subsequence to prawdopodobnie najlepsze, co możesz zrobić.

to jest u góry mojej głowy, więc może (przeczytaj prawdopodobnie nie jest: P) poprawne: Oczywistą dolną granicą dla tego problemu jest O (n), ponieważ przynajmniej musisz przeczytać każdą liczbę raz . Załóżmy jednak, że istniał algorytm, który działał w czasie O (n). Następnie możesz po prostu wstawiać elementy nieczynne w kolejności w czasie liniowym, ale najlepszy algorytm sortowania porównawczego ma dolną granicę O (nLogn), więc jest to sprzeczność. (w przeciwnym razie istnieją metody sortowania bez porównania, takie jak sortowanie wiadro lub radix, które używają dużej ilości pamięci lub wykorzystują rozmiar sortowanych liczb ...)