Co oznaczają „dane niepatologiczne”?

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?

Dane patologiczne powinny być danymi, które powodują, że coś pójdzie nie tak w zamierzonym obliczeniu. Można go nazwać patologicznym, gdy jest wystarczająco rzadki w rzeczywistych zastosowaniach, dzięki czemu przez większość czasu wszystko działa OK. Czasami można to uczynić matematycznie bardziej precyzyjnym (na przykład z prawdopodobieństwami), ale użycie słowa patologiczny jest często nieformalne.

Na przykład sałatka pomidorowa i keczup to doskonałe jedzenie, z wyjątkiem osób patologicznych, czyli tych, którzy są uczuleni na pomidory. W niektórych przypadkach może faktycznie zabić. Ale osoby uczulone na pomidory są bardzo rzadkie, dlatego dania pomidorowe są uważane za doskonałe, z wyjątkiem przypadków patologicznych.

$O(n^2)$$O(n \lg n)$$O(n \lg n)$$O(\lg n)$$O(n)$ do sortowania po scaleniu.

$O(n^2)$

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.

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.