El costo amortizado solo tiene sentido sobre cierto conjunto de operaciones.
Por ejemplo, si el costo de realizar n operaciones es nlog (n), entonces el costo amortizado * de cada operación * es log (n). No hay aceleración mágica, solo un cambio de las unidades que usas para describir el tiempo.
Si está buscando agregar a un árbol, entonces el costo de agregar un artículo podría ser log (k) si k es el número de artículos en el árbol y el árbol está equilibrado
- ¿En qué circunstancias necesitaría un desarrollador web utilizar estructuras de datos como Listas vinculadas, BST y Gráficos?
- ¿Qué temas de informática utilizan el cálculo? ¿Cuáles son algunos otros subcampos utilizados en informática?
- ¿Cuáles son los cursos de pregrado más importantes para alguien que planea obtener un doctorado en aprendizaje automático?
- Quiero aprender matemáticas programando. ¿Cuáles son los proyectos de programación simples pero geniales que requerirían conocimiento de álgebra, cálculo, probabilidad, etc.?
- Sistemas distribuidos: ¿El resultado de imposibilidad de FLP y el teorema de CAP de Brewer son básicamente equivalentes?
Como comentario adicional, tenga en cuenta que el registro aquí para un árbol binario representaría el registro base 2 en lugar del registro normal basado en 10. Matemáticamente, no importa cuál elija porque difieren en una constante y, por lo tanto, son equivalentes, pero log 2 (k ) señala mejor la derivación.
En su ejemplo, agregar k a un contador es en realidad O (1), no O (k), por lo que hacer esto n veces podría expresarse como O (n) u O (1) costo amortizado por artículo sobre n artículos, aunque la segunda descripción sería un poco tonta en este caso porque no hay necesidad de lidiar con costos variables.
