Jestem zdezorientowany co do złożoności czasu tablicy hash wielu artykułów stwierdza, że są one "zamortyzowanym O (1)" niepoprawnym porządkiem O (1), co to oznacza w prawdziwych aplikacjach. Jaka jest przeciętna złożoność czasu operacji w tabeli mieszania, w rzeczywistości nie w teorii, i dlaczego operacje nie są prawdziwe O (1)?Złożoność czasowa tabeli mieszania
W przypadku niektórych zastosowań tabel mieszania niemożliwe jest wcześniejsze utworzenie ich z "właściwym" rozmiarem, ponieważ nie wiadomo, ile elementów będzie musiało być przechowywanych jednocześnie podczas okresu istnienia tabeli. Jeśli chcesz zachować szybki dostęp, musisz zmieniać rozmiar tabeli od czasu do czasu, gdy liczba elementów rośnie. To zmienianie rozmiaru zajmuje liniowy czas w odniesieniu do liczby elementów już znajdujących się w tabeli i jest zwykle wykonywane przy wstawianiu, gdy elementy liczbowe przekraczają próg.
Te operacje zmiany rozmiaru mogą być wykonywane na tyle rzadko, że zamortyzowany koszt wstawienia jest nadal stały (postępując geometrycznie dla rozmiaru tabeli, na przykład podwajając rozmiar przy każdej zmianie rozmiaru). Ale jedno wstawienie od czasu do czasu zabiera O (n), ponieważ powoduje zmianę rozmiaru.
W praktyce nie stanowi to problemu, jeśli nie tworzysz twardych aplikacji czasu rzeczywistego.
Nie chodzi tylko o rozmiar - to także mieszania mieszania. Są różne sposoby radzenia sobie z nimi, ale cokolwiek zrobisz, nie wydarzy się w O (1) czasie. Przeciętny przypadek jest w praktyce nadal bliski O (1), chyba że tablica hash staje się całkiem pełna. – Jords
@Jords Nie wiem, co znaczy "blisko O (1)".Poza tym jestem całkiem pewny, że "zamortyzowany O (1)" znaleziony w literaturze odpowiada hipotezom na funkcji mieszania, gdzie głębokość wiadra pozostaje poniżej ustalonego związanego, a więc stałego czasu. Ponieważ jeśli wyszukiwanie bez zmiany rozmiaru nie było stałym czasem, amortyzowane wyszukiwanie nie byłoby również stałym czasem. –
Nie można z góry wiedzieć, ile kolizji dostaniesz za pomocą funkcji skrótu, a także takich, które wymagają zmiany rozmiaru. Może to dodać element nieprzewidywalności do wydajności tabeli mieszającej, powodując, że nie jest to prawda O (1). Jednak praktycznie wszystkie implementacje tabel hash oferują O (1) na ogromnej, ogromnej większości wkładek. Jest to to samo, co wstawianie tablicy - jest to O (1), chyba że musisz zmienić rozmiar, w takim przypadku jest to O (n), a także niepewność kolizji.
W rzeczywistości kolizje hash są bardzo rzadkie i jedynym warunkiem, w którym trzeba by się martwić o te szczegóły, jest sytuacja, gdy określony kod ma bardzo wąskie okno czasowe, w którym musi działać. Dla praktycznie każdego przypadku użycia, tablice skrótów to O (1). Bardziej imponujące niż wstawianie O (1) jest wyszukiwanie O (1).
cóż, wyszukiwanie O (1) dotyczy również tablic –
Wkładanie wartość do tabeli mieszania trwa, w przypadku przeciętnego, O (1) Czas. Funkcja hash jest obliczana, bucked jest wybierany z tabeli skrótów, a następnie element jest wstawiany. W najgorszym przypadku, wszystkie elementy będą miały przypisaną wartość do tej samej wartości, co oznacza, że cała lista zasobników musi być przesuwana lub, w przypadku adresowania otwartego, cała tabela musi być sondowana aż do pustego miejsca jest znalezione. więc w najgorszym przypadku, wprowadzenie trwa O (n)
patrz: http://www.cs.unc.edu/~plaisted/comp550/Neyer%20paper.pdf (tablica mieszająca Sekcja)
Wiąże się to, ale nie dokładnie w tej samej kwestii: http://stackoverflow.com/ pytania/2369467/dlaczego-są-tabliczki-ekspansje-zwykle-zrobione przez podwojenie-size –
To pomaga odpowiedzieć na wstawienie, ale nie wyjaśnia nic na temat innych operacji, jestem najbardziej zainteresowany wyjaśnieniem, jak złożoność czasowa odnośników w tablicy mieszającej – marme
W niektórych hipotezach funkcji mieszającej wyszukiwanie jest prawdziwym czasem O (1) dla większości implementacji tablic mieszańcowych. Rzeczywiście, w niektórych implementacjach z ograniczoną głębokością czerpaka jest on stały z założenia. –