Czy możemy uzyskać posortowaną listę z posortowanej macierzy w

Jestem zmieszany. Chcę udowodnić, że problem sortowania macierzy przez , tj. Wiersze i kolumny są w porządku rosnącym, to . Kontynuuję, zakładając, że można to zrobić szybciej niż i próbuję złamać dolną granicę Dla porównań potrzebnych do posortowania m elementów. Mam dwie sprzeczne odpowiedzi: $n$ $n$ $\Omega(n^2\log n)$ $n^2\log n$ $\log(m!)$

możemy uzyskać posortowaną listę elementów z posortowanej macierzy w /math/298191/lower-bound-for-matrix-sorting/298199?iemail = 1 # 298199 $n^2$ $O(n^2)$
nie można uzyskać posortowanej listy z matrycy szybciej niż $Ω(n^2\log(n))$ /programming/4279524/how-to-sort-amxn-matrix-which-has- wszystkie-m-rzędy-posortowane -i-n-posortowane

Który jest prawidłowy?

time-complexity lower-bounds matrices sorting asymptotics user2038833
źródło

Nawiasem mówiąc, irytuje mnie, gdy widzimy twierdzenia, że „sortowanie to ”, ale które nie określają modelu wejściowego i modelu obliczeniowego. Sortowanie porównawcze to . Sortowanie może być na ogół szybsze, na przykład dla łańcuchów (jeśli jest całkowitą długością wejściową) lub liczb całkowitych (w niektórych modelach obliczeniowych, które pozwalają na operacje arytmetyczne na liczbach całkowitych w czasie).

Ω (n \log n)

$\Omega(n\log n)$

Ω (n \log n)

$\Omega(n\log n)$

n

$n$

David Eppstein,

Aby być jeszcze bardziej pedantycznym: Sortowanie porównawcze nie jest , ponieważ sortowanie porównawcze nie jest funkcją od do . Sortowanie wymaga czasu w dowolnym binarnym modelu drzewa decyzyjnego (nie tylko porównań).

Ω (n \log n)

$\Omega(n\log n)$

R

$\mathbb{R}$

R

$\mathbb{R}$

Ω (n \log n)

$\Omega(n\log n)$

Jeffε

Odpowiedzi:

Dolna granica jest poprawna (2) - nie możesz tego zrobić lepiej niż i (1) jest oczywiście błędne. Najpierw określmy, czym jest posortowana macierz - jest to macierz, w której elementy w każdym rzędzie i kolumnie są sortowane w kolejności rosnącej. $\Omega(n^2 \log n)$

Łatwo jest teraz sprawdzić, czy każda przekątna może zawierać elementy, które są w dowolnej kolejności - wystarczy, aby były wystarczająco duże. W szczególności sortowanie macierzy oznacza sortowanie każdej z tych przekątnych. th przekątna ma wpisy, a co za tymmożliwe zamówienie. Jako taka, posortowana macierz może zdefiniować co najmniej różne zamówienia. Łatwo jest teraz sprawdzić, czy , co sugeruje, że w modelu porównawczym (i jak wskazuje poniżej Jeff, w każdym binarnym modelu drzewa decyzyjnego) przynajmniej jest to dolna granica w czasie sortowania. $i$ $i$ $i!$ $X = \prod_{i=1}^n i!$ $\log_2 X = \Omega(n^2 \log n)$

Sariel Har-Peled
źródło

Ponownie, w każdym modelu drzewa decyzji binarnych, nie tylko porównań.

Jeffε