Dlaczego nie da się stworzyć takiego algorytmu?

0

Zgaduje że że z tą pamięcią chodzi Ci o to że do reprezentacji liczby która zostanie użyta do zapisywania indeksów potrzeba log(n) pamięci gdzie, n to liczba elementów. Ma to jakiś sens, tyko ze mówiłeś o teoretycznym ograniczeniu a nie o praktycznym. Każdy podręcznik od algorytmów i struktur danych zaczyna sie od tego że notacja O(), skupia się na tym ile trzeba "wykonać operacji znaczących", a nie jak one są wykonywane. Jeśli można pominąć sposób reprezentacji indeksów, używać odwrotności liczb rzeczywistych z zakresu (0;1> czyli np 2 to 1/ 0.5(0). ten zakres zawiera wszystkie liczby naturalne, dodatkowo każda liczba z tego zakresu ma taką samą długość reprezentacji. A ponieważ korzystając z takiej reprezentacji każda liczba naturalna wymaga stałej ilości pamięci, to zapisanie indeksu wymaga O(1) a nie O(long n) pamięci.
Założeń o nieskończenie długiej reprezentacji liczb korzystał turing w swojej pracy o... maszynie turinga, wiec nawet nie próbuj na pisać że tego nie da się na takiej reprezentacji prowadzić obliczeń.

0

Nie interesuje mnie teoretyzowanie, lecz dowód w postaci jawnej, tz. algorytmu in-situ, który ma złożoność poniżej n^2.

Dodatkowe uwaga:
algorytm sortowania 'in-situ', to taki, który nie wymaga dodatkowej pamięci, zależnej od n.
Inaczej: algorytm ma używać stałą ilość pamięci, niezależnie od rozmiaru sortowanej tablicy!

Qsort tego warunku nie spełnia... tu jest koniecznie: c*log(n) extra ramu, co zależy od n, czyli metoda nie jest in-situ.
Stogowe - podobnie.
Scalanie serii - też typu nlogn - i też używa wprost ekstra n ramu, więc tak samo odpada...

3

Jak się tak upierasz, by ignorować linki do publikacji naukowych, jakie dostałeś od Shaloma, to łap link do Wikipedii: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
Znajdziesz tam m.in. omówienie jednej z ww. publikacji:

Katajainen et al. present an algorithm that requires a constant amount of working memory: enough storage space to hold one element of the input array, and additional space to hold O(1) pointers into the input array. They achieve an O(n log n) time bound with small constants […].

Chciałbym też zauważyć, że zmieniasz temat co chwila:

  1. Nie ma sortowania bez porównywania.
  2. Jedynie liczby można porównywać i szeregować.
  3. W przypadku zespolonych nie istnieje rel. mniejszości, podobnie jak w przypadku dowolnych wektorów.
  4. Mniejszość to jest relacja liczb — skalarów, i koniec!
  5. Nie istnieje algorytm sortowania typu in-situ o złożoności mniejszej od n².

Czyli jedna bzdura za drugą, skaczesz sobie na kolejne jak tylko ktoś Ci poprzednią zdementuje. Hmm… Gdyby tylko było jakieś zgrabne określenie na tego typu zachowanie w Internecie…

0

Nadal czekam... na ten algorytm in situ, który sortuje szybciej od o(n^2).

Podpowiedź: nazwa tego algorytmu padła tu już wielokrotnie. :)

0

Zamykam wątek bo odpowiedzi padły, a nie ma co karmić trolla idioty @fol :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1