Intuición detrás del árbol de extensiones (árboles autoejactos)

Question

Estoy leyendo los conceptos básicos de los árboles de entrega. El costo amortizado de una operación es o (log n) sobre N operaciones. Una idea básica aproximada es que cuando accede a un nodo, lo extiende, es decir, lo lleva a la raíz, por lo que la próxima vez se accede rápidamente y también si el nodo era profundo, mejora el equilibrio del árbol.

No entiendo cómo el árbol puede realizar O (log n) amortizado para esta entrada de muestra:

Digamos que un árbol de N nodos ya está construido. Mis próximas operaciones N son N Reads. Accedo a un nodo profundo por ejemplo en profundidad n. Esto toma o (n). Es cierto que después de este acceso, el árbol se equilibrará. Pero digamos cada vez que accedo al nodo profundo más actual. Esto nunca será menor que o (log n). Entonces, ¿cómo podemos compensar la primera operación costosa o (n) y traer el costo amortizado de cada lectura como o (log n)?

Gracias.

Answer 1

Suponiendo que su análisis sea correcto y las operaciones son O(log(n)) por acceso y O(n) la primera vez...

Si siempre accede al elemento Bottommost (usando algún tipo de oráculo en el peor de los casos), una secuencia de a los accesos tomarán O(a*log(n) + n). Y así el costo amortizado por operación es O((a*log(n) + n)/a)=O(log(n) + n/a) o solo O(log(n)) A medida que el número de accesos crece.

Esta es la definición de rendimiento/tiempo/espacio asintótico de casos promedio, también llamado "rendimiento/tiempo/espacio amortizado". Estás pensando accidentalmente que un solo O(n) paso significa que todos los pasos son al menos O(n); Uno de esos pasos es solo una cantidad constante de trabajo a largo plazo; la O(...) está ocultando lo que realmente está sucediendo, que está tomando el límite de [total amount of work]/[queries]=[average ("amortized") work per query].

Esto nunca será menor que o (log n).

Tiene que ser para obtener O(log n) rendimiento medio. Para obtener intuición, el siguiente sitio web puede ser bueno: http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml específicamente la imagen http://users.informatik.uni-halle.de/~jopsi/dinf504/splay_example.gif - Parece que mientras realiza el O(n) Operaciones, mueve el camino que buscó arrugando hacia la parte superior del árbol. Probablemente solo tengas un número finito de este O(n) Operaciones para realizar hasta que todo el árbol esté equilibrado.

Aquí hay otra forma de pensarlo:

Considere un árbol de búsqueda binario desequilibrado. Puedes gastar O(n) tiempo balanceándolo. Suponiendo que no le agregue elementos*, se necesita O(log(n)) tiempo amortizado por consulta para obtener un elemento. El costo de configuración de equilibrio se incluye en el costo amortizado porque es efectivamente una constante que, como se demuestra en las ecuaciones en la respuesta, desaparece (está eclipsada) por la cantidad infinita de trabajo que está haciendo. (*Si le agregas elementos, necesitas un árbol de búsqueda binario de equilibrio, uno de los cuales es un árbol de mantequilla)