Czy ktoś zna Yijie Han , algorytm sortowania liczb całkowitych? Wynik ten pojawia się w dość krótkim artykule ( Sortowanie deterministyczne w czasie i przestrzeni liniowej . J. Alg. 50: 96–105, 2004), który zasadniczo skleja ze sobą wiele wcześniejszych wyników, z odpowiednimi adaptacje. Mój problem polega na tym, że jest napisany raczej machaniem ręką, bez wchodzenia w szczegóły. Opiera się w dużej mierze na poprzednich artykułach, wyróżniających się wśród nich innym artykule Hana ( Ulepszone szybkie sortowanie liczb całkowitych w przestrzeni liniowejO ( n log dziennika n ). Informacje i obliczenia 170 (1): 81–94) napisane w bardzo podobnym stylu. Mam poważne trudności ze zrozumieniem tych dwóch artykułów, zwłaszcza sposobu, w jaki dostosowują i wykorzystują poprzednie wyniki. Byłbym wdzięczny za każdą pomoc.
Jest to oczywiście zbyt ogólne i niejasne, aby uznać je za właściwe pytanie, ale mam nadzieję rozwinąć dyskusję na temat kilku ściśle określonych pytań i odpowiedzi.
Na wstępie oto moje pierwsze konkretne pytanie. W Lemat 2 informacji. Komp. W dokumencie znajduje się rekurencyjny algorytm czasowy służący do znajdowania m-tej najmniejszej liczby całkowitej w zestawie małych liczb całkowitych upakowanych każdy w słowa RAM. Opis algorytmu nie wspomina o tym, jak obsługiwany jest przypadek podstawowy k = O (n) . W takim przypadku wymagane jest dokonanie wyboru w czasie O (\ log k) . Jak można to zrobić?n k k = O ( n )
Odpowiedzi:
Zastanawiałem się tylko nad tym samym.
Na szczęście udało mi się znaleźć artykuł w czasopiśmie opublikowany w 2011 r., Który wyjaśnia to właśnie; co więcej, nie potrzebujesz subskrypcji, aby ją zobaczyć: implementacja i analiza wydajności wykładniczego sortowania drzew
Polecam przeczytać cały artykuł, aby dowiedzieć się, jak można go wdrożyć i lepiej zrozumieć jego leżącą u podstaw teorię. Pokazuje także, w jaki sposób drzewa wykładnicze zestawiają się z drzewami szybkiego sortowania i drzewami binarnymi. Oto odpowiedni fragment związany z czasem Hana , przestrzenią liniową, algorytmem sortowania liczb całkowitychO ( n loglogn ) :
[6] Y. Han, Sortowanie deterministyczne w czasie O (n log log n) w czasie i przestrzeni liniowej, 34. STOC, 2002.
[8] A. Andersson, Szybkie deterministyczne sortowanie i wyszukiwanie w przestrzeni liniowej, IEEE Symposium on Foundations of Computer Science, 1996.
źródło
nie jestem pewien odpowiedzi (nie przeszedłem przez papier), ale myślę, że to powinno pomóc. Liczby są upakowane w jednym słowie, więc operacje na jednym słowie zajmują O (1). Jeśli są, powiedzmy, k liczb bitów h każda, to rozmiar słowa zależy od k, h, która z kolei zależy również od zakresu liczb. Dlatego stosujemy techniki redukcji zasięgu, które mogą zmniejszyć zakres liczb, aby wiele liczb mieściło się w jednym słowie. Następnie tworząc odpowiednie maski bitowe, możemy znaleźć oddzielne większe liczby całkowite od krótszych, biorąc pod uwagę dwa słowa na raz. Można to zrobić w czasie O (1). (Ontuition: do tego każda liczba przechowywana w słowie ma bit flagi związany z nim, a następnie odejmujemy dwa słowa ... jeśli bit flagi idzie, to jest mniejsza liczba).
Podobnie, używając powyższego, możemy również sortować dowolne słowo zawierające k liczb w czasie O (log k) (sortowanie bitoniczne).
Edycja: Algorytm sortowania liczb 2k z zakresu od 0 do m-1 upakowanych w słowie, gdzie każda liczba przyjmuje rozmiar L = log (m + k) +2.
Powtórz dla t = log k do 0.
Część 1 - podziel oryginalne słowo Z na dwa słowa A i B.
B = Z- (Z&M).
Część 2
M = M- (M przesunął lewe miejsca L-1).
MIN = (B&M) LUB (A- (A&M))
MAX = (A&M) LUB (B- (B&M))
Wreszcie odpowiednio ORing MAX i MIN wracamy Z.
Dałem szkic, mam nadzieję, że możesz uzupełnić wymagane szczegóły.
źródło