Extraños resultados al trazar (Cormen) Inserto de árbol rojo-negro

Question

Implementé en árboles Rojo-Negro en Python de acuerdo con el seudo código en Cormen's Introduction to Algorithms.

quería ver a mis propios ojos que mi insert es realmente O(logn) así que trazan el tiempo que toma para insertar n=1, 10, 20, ..., 5000 nodos en el árbol.

Este es el resultado:

el eje x es xn y la y eje x es el tiempo que se tardó en milisegundos.

Para mí, el gráfico parece más lineal que logarítmico. ¿Qué puede explicar eso?

Answer 1

Ok, entonces el gráfico muestra una medida del costo de insertar n elementos en su árbol, donde el eje x es cuántos elementos hemos insertado, y el eje y es el tiempo total.

Llamemos a la función que suma el tiempo que se tarda en insertar n elementos en el árbol f(n).

Entonces podemos obtener una idea aproximada de lo que f podría ser:

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. 

Debido a cómo funcionan los registros, podemos colapsar 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 

Podemos echar un vistazo a Wikipedia para ver un graph de como se ve log(n!). Eche un vistazo al gráfico en el artículo. Debería verte bastante familiar.:)

Es decir, creo que has hecho esto por casualidad:

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 

y se representa el tiempo total para construir el árbol de tamaño n, en lugar del costo individual de la inserción de un elemento en un árbol de tamaño n:

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

---

Chris Taylor señala en los comentarios que si se trazan f(n)/n, verá un gráfico de registro. Eso es porque una aproximación bastante ajustada a log(n!) es n*log(n) (vea la página de Wikipedia). Así podemos volver a nuestro límite:

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

y obtenemos:

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

y ahora es debería ser más fácil de ver que si se divide f(n) por n, su gráfico será acotado superiormente por la forma de un logaritmo.

Answer 2

5000 podría no ser lo suficientemente grande como para "ver" realmente el logaritmo - intente ejecutar en 50000 y 500000. Si toma dos segundos y veinte segundos, entonces el crecimiento lineal tiene sentido. Si toma menos, entonces logarítmico tiene sentido. Si acercas lo suficiente la mayoría de las funciones "simples", los resultados se ven bastante lineales.

Answer 3

Siempre hay un puñado de especulaciones sobre cualquier pregunta "por qué". Sospecho que los saltos que está viendo están relacionados con la administración de la memoria del sistema. Si el sistema tiene que asignar un espacio de memoria más grande para un crecimiento continuo, agregaría una cantidad de tiempo dada para completar el procesamiento de todo el programa. Si agregaste un campo de 'carga útil' a tus nodos, aumentando así la cantidad de espacio de almacenamiento necesario, y estoy en lo cierto, los saltos ocurrirán con más frecuencia.

Buen gráfico, por cierto.