Wziąłem lekcję algorytmów na Coursera. Tak powiedział profesor w filmie o tabelach skrótów
Prawdą jest, że w przypadku danych niepatologicznych dostaniesz operacje o stałym czasie w odpowiednio zaimplementowanej tabeli skrótów.
Co oznaczają „dane niepatologiczne”? Czy możesz podać jakieś przykłady?
źródło
Dane patologiczne to dane, które spowodują złe działanie algorytmu. W przypadku tablic skrótów dane patologiczne to dane, które powodują kolizje. To oczywiście zależy od użytej funkcji skrótu.
Na przykład, jeśli funkcja mieszania dodaje znaki razem:
hash("abcd") = 'a' + 'b' + 'c' + 'd'
. Dane patologiczne wyglądają następująco:{"abcd", "dcba", "cbda", ...}
. Każda permutacja"abcd"
will hash do tej samej pozycji, więc skończysz z połączoną listą, której starałeś się w pierwszej kolejności uniknąć.Dane niepatologiczne to dane, które nie są patologiczne.
źródło
inny sposób myślenia na ten temat: klucze skrótu są jak osobne „pojemniki” zawierające dane. można się spodziewać / mieć nadzieję, że dane są równomiernie rozłożone na wszystkie pojemniki, „zrównoważone”. w przypadku danych niepatologicznych każdy pojemnik zawiera / zawiera mniej więcej taką samą ilość danych. jeśli dane są patologiczne (algorytm mieszania klucza wrt), wszystko „gromadzi się” w mniejszej liczbie pojemników, a niektóre pojemniki mają znacznie mniej. jest to nieefektywne, ponieważ czas wyszukiwania zwiększa się (a wydajność spada / zbiega się z czasem wyszukiwania nieposortowanej listy), gdy pojemniki są wypełnione większym. należy zauważyć, że sama zmiana kluczowego algorytmu skrótu może zmienić dane z „patologicznego” na „niepatologiczny” lub odwrotnie, stąd znaczenie algorytmu skrótu.
istnieje również wiele innych algorytmów, dla których można zastosować rozróżnienie między „patologicznym a niepatologicznym”, przy czym w zasadzie „dane patologiczne” sprawiają, że algorytm działa w gorszym przypadku (np. koncepcja jest również stosowana w przypadku algorytmów sortujących). jak widać, jest to koncepcja statystyczna. również w przypadku tego samego problemu dane „patologiczne” dla jednego algorytmu mogą nie być „patologiczne” dla innego. itp.
źródło