Dziwne wyniki przy kreśleniu (Cormen) Czerwono-czarne wstawienie drzewa

Question

Zaimplementowałem w czerwono-czarnych drzewach w Pythonie zgodnie z pseudo kodem w Cormen's Introduction to Algorithms.

chciałem zobaczyć na własne oczy, że moje insert jest naprawdę O(logn) więc wykreślono czas potrzebny do wstawienia n=1, 10, 20, ..., 5000 węzłów w drzewie.

Jest to wynikiem:

x -działający jest n i y -działający jest czas zajęło w milisekund.

Dla mnie wykres wygląda bardziej liniowo niż logarytmicznie. Co może to wyjaśnić?

Answer 1

OK, więc na wykresie wyświetlany jest pomiar kosztów wstawiania elementów n do drzewa, gdzie oś x jest liczbą wprowadzonych elementów, a oś y jest czasem całkowitym.

Połączmy funkcję, która sumuje czas potrzebny do wstawienia n elementów do drzewa f(n).

Wtedy możemy uzyskać z grubsza co f może wyglądać następująco:

f(1) < k*log(1)     for some constant k. 

f(2) < k*log(1) + k*log(2)  for some constant k 

... 

f(n) < k * [log(1) + log(2) + ... + log(n)] for some constant k. 

Ze względu na sposób działania dzienniki, możemy zwinąć log(1) + ... + log(n):

f(n) < k * [log(1*2*3*...*n)]  for some constant k 

f(n) < k * log(n!)    for some constant k 

Możemy przyjrzeć Wikipedia aby zobaczyć, jak wygląda graph tego, co . Spójrz na wykres w artykule. Powinien wyglądać całkiem znajomo.:)

Oznacza to, że myślę, że zrobiłem to przez przypadek:

for n in (5000, 50000, 500000): 
    startTime = ... 
    ## .. make a fresh tree 
    ## insert n elements into the tree 
    stopTime = ... 
    ## record the tuple (n, stopTime - startTime) for plotting 

i wykreślono całkowity czas, aby zbudować drzewo rozmiarze n, zamiast indywidualnego kosztu wkładając jeden element w drzewie o rozmiarze N:

for n in range(50000): 
    startTime = ... 
    ## insert an element into the tree 
    stopTime = ... 
    ## record the tuple (n, stopTime - startTime) for plotting 

---

Chris Taylor zauważa w komentarzach, że jeśli działka f(n)/n, zobaczysz wykres dziennika. To dlatego, że dość ciasne przybliżenie do log(n!) to n*log(n) (zobacz stronę Wikipedii). Tak więc możemy wrócić do naszego bound:

f(n) < k * log(n!)    for some constant k 

a otrzymasz:

f(n) < k * n * log(n)    for some constant k 

a teraz to powinno być łatwiej zobaczyć, że jeśli podzielić f(n) przez n, Twój wykres będzie ograniczony z góry przez kształt logarytmu.

Answer 2

5000 może nie być wystarczająco duży, aby naprawdę "zobaczyć" logarytm - spróbuj uruchomić pod numerami 50000 i 500000. Jeśli zajmuje to dwie sekundy i dwadzieścia sekund, wówczas wzrost liniowy ma sens. Jeśli zajmuje mniej, to logarytmiczna ma sens. Jeśli zbliżysz się wystarczająco do większości "prostych" funkcji, wyniki będą wyglądały dość liniowo.

Answer 3

Zawsze istnieje kilka spekulacji na dowolne pytanie "dlaczego". Podejrzewam, że skoki, które widzisz, są związane z zarządzaniem pamięcią systemową. Jeśli system musi przeznaczyć większą przestrzeń pamięci na ciągły wzrost, doda to określoną ilość czasu do zakończenia przetwarzania całego programu. Jeśli dodasz pole "ładunek" do twoich węzłów, zwiększając tym samym ilość potrzebnego miejsca do przechowywania, i jestem w porządku, skoki będą się zdarzać częściej.

Przyjemny wykres, przy okazji.