Scalanie list delikatnych obiektów

Tło: Chao Xu opublikował kiedyś pytanie: „ Czy są znane algorytmy sortowania porównawczego, które nie ograniczają się do sieci sortujących, tak że każdy element jest porównywany razy?$O(\log n)$ ”. Wygląda na to, że trochę utknęliśmy w tym problemie; Omówiłem ten sam problem z Valentinem Polczukiem w 2009 roku i nigdzie nie doszło.

Aby uzyskać świeże pomysły, próbowałem znaleźć najprostsze możliwe pytanie, które ma podobny smak i nie jest całkowicie trywialne. Stąd następujące pytanie.

Pytanie: Otrzymujesz dwie posortowane listy, z których każda zawiera elementów. Czy możesz scalić listy, aby każdy element był porównywany tylko razy?$n$$O(1)$

Naturalnie, wynik powinien być posortowaną listą zawierającą wszystkie elementy .$2n$

[Okazało się to trywialne, odpowiedź brzmi „nie”.]

Pytanie 2: Otrzymujesz dwie posortowane listy, z których każda zawiera elementów. Czy możesz scalić listy, aby każdy element był porównywany tylko razy, jeśli możesz odrzucić niewielką część elementów ?$n$$O(1)$

Dokładniej, wynik powinien być posortowaną listą zawierającą elementy oraz „kosz na śmieci” zawierający elementy . Jak małe możesz zrobić wartość ? Uzyskanie jest banalne. Coś w rodzaju powinno być wykonalne w prosty sposób. Ale czy możesz uzyskać ?T ( n ) T ( n ) T ( n ) = n T ( n ) = n / 100 T ( n ) = o ( n $2n-T(n)$$T(n)$$T(n)$$T(n) = n$$T(n) = n/100$$T(n) = o(n)$

Uwagi:

• Używamy tutaj modelu porównawczego. Tylko algorytmy deterministyczne, interesują nas gwarancje najgorszego przypadku.

• Zauważ, że obie listy zawierają dokładnie elementów. Gdybyśmy mieli jedną listę z elementami, a drugą z elementem, odpowiedź brzmi „nie”; Jeśli jednak obie listy są długie, wydaje się, że można wykonać „równoważenie obciążenia”.n $n$$n$$1$

• Tym razem dowolny algorytm jest poprawny. Jeśli twój algorytm używa sieci sortujących jako elementu składowego, jest w porządku.

• Na początek, oto prosty algorytm, który porównuje każdy element maksymalnie 200 razy: Po prostu użyj standardowego algorytmu scalania, ale zachowaj liczniki dla nagłówków list. Gdy osiągniesz 200, odrzuć element. Teraz dla każdego odrzucanego elementu z powodzeniem umieściłeś 200 elementów w tablicy wyjściowej. Dlatego osiągnąłeś .$T(n) = n/100$

Nie, taki algorytm nie może istnieć.

Załóżmy, porównania na element są dozwolone.$t$

Na początek rozważ sytuację łączenia dwóch list, jednej o rozmiarze pierwszym, a drugiej o rozmiarze . Możliwe są możliwych wyników, a prosty argument przeciwnika pokazuje, że element na małej liście musi uczestniczyć w porównaniach i ten element musi trafić do kosza.2 t + 1 t + $2^t$$2^t+1$$t+1$

Z tego łatwo jest zbudować instancję z dwiema listami rozmiaru która składa się z tak małych sytuacji, a zatem elementy muszą trafić do kosza.n / 2 t n / 2 $n$$n/2^t$$n/2^t$

Dlatego dopóki jest stałe, nie można mieć śmieci .o ( n $t$$o(n)$

Na marginesie wydaje się, że możliwe jest dopasowanie tego ograniczenia przez algorytm, w którym każdy element jest porównywany z mniej więcej logiem wielkości otaczającej części drugiej listy. Jeśli jest to interesujące, postaram się ustalić szczegóły.