Imagine que tiene un negocio y necesita comprar un automóvil. El auto cuesta 10.000 €. Si lo compra, tendrá que hacer un pago de € 10,000 este año.
Sin embargo, planea usar el automóvil durante los próximos diez años. Hacer funcionar el automóvil durante un año cuesta otros 1.000 €
Ahora, hay dos formas posibles de ver la situación anterior. La primera forma es la que utilizamos anteriormente: hay un año con muchos gastos y otros nueve años con una cantidad menor de gastos.
- ¿Cuál es una explicación simple para el filtrado anisotrópico?
- ¿Puedes citar buenos ejemplos de aplicaciones de aprendizaje automático en el contexto de ciudades inteligentes?
- Si podemos navegar por los contenidos de Internet en el sandbox (como el navegador Chrome), ¿por qué necesitamos establecer otros valores?
- ¿Es mejor trabajar en una aplicación para algoritmos de aprendizaje automático (por ejemplo, biología computacional), en lugar de trabajar en ML central, ya que el campo ya está maduro y hay menos espacio para mejorar?
- Como científico de datos, ¿usa más R o Python o es más o menos lo mismo?
La segunda forma es resumirlo todo. Los gastos totales de comprar un automóvil y usarlo durante diez años suman 20.000 €. Por lo tanto, puede decir que el automóvil me costará 2.000 € por año . Esto es amortización .
Ahora, podemos hacer lo mismo con algoritmos y estructuras de datos. En muchos casos, todos los pasos de un algoritmo / todas las ejecuciones de un método de una estructura de datos tienden a ejecutarse aproximadamente al mismo tiempo. En tales casos, es fácil obtener un buen límite superior en la complejidad del tiempo: es el número de pasos, multiplicado por el tiempo máximo de ejecución de un solo paso.
Sin embargo, en algunos casos podemos encontrarnos con situaciones que se parecen al ejemplo del automóvil: hay algunas operaciones costosas raras y muchas más baratas. En tales casos, el método anterior da una estimación que es demasiado alta. Un método más preciso es la complejidad del tiempo amortizado : para dar un límite superior a la complejidad del tiempo, tratamos de mostrar que aunque algunas de las operaciones pueden ser costosas, la suma (o, equivalentemente, el promedio ) de sus tiempos de ejecución siempre Tiene que ser pequeño.
Las siguientes declaraciones son equivalentes:
- Este programa tiene una complejidad de tiempo amortizada O (f (n)) por operación.
- Aunque algunas operaciones realizadas por este programa pueden tomar significativamente más que f (n) pasos, el número total de pasos en una secuencia de n operaciones será O (n * f (n)).
- Si t (n) es la complejidad de tiempo más desfavorable de nuestro programa si realiza n operaciones, entonces t (n) / n puede estar limitado desde arriba por f (n).
Ejemplo de esas tres declaraciones para una estructura de datos particular (std :: vector :: push_back – cppreference.com):
- La complejidad de tiempo amortizada de vector :: push_back al insertar elementos en un vector inicialmente vacío es O (1).
- Si tomamos un vector vacío y llamamos push_back n veces, algunas de las llamadas serán rápidas y otras lentas. Pero a pesar de que hay llamadas lentas, tenemos la garantía de que toda la secuencia de n push_backs se ejecutará en tiempo O (n).
- Si amortizamos el costo de todos los n push_backs, obtenemos que en promedio cada push_back solo toma un número constante de pasos.
El método de contabilidad y el método potencial son dos formas particulares de mostrar que las afirmaciones como las anteriores sobre vector :: push_back son verdaderas. Estos dos métodos están estrechamente relacionados. Ambos corresponden a la metáfora de ahorrar para cosas que quieres hacer en el futuro, usando una alcancía.
En el método contable nos centramos en cómo cambia el contenido de la hucha en cada paso. Este es el punto de vista elegido en el ejemplo detallado a continuación. En el método potencial nos enfocamos en cómo el potencial actual (es decir, el valor en la hucha) se puede calcular directamente desde el estado actual del algoritmo / estructura de datos.
Suponga que desea mostrar que una secuencia de n operaciones tiene un costo amortizado f (n) por operación. Si está mostrando este reclamo utilizando el método de contabilidad, procederá de la siguiente manera:
Imagine que cada paso de cálculo cuesta 1 moneda. Antes de cada operación, obtienes f (n) monedas. Su objetivo es demostrar que, independientemente de cómo se vean las operaciones, nunca puede quedarse sin dinero.
Más precisamente: comienzas con una alcancía vacía. Ahora, cada vez que realiza una operación rápida que solo toma x <f (n) pasos, ahorra algo de tiempo, por lo tanto, coloca monedas f (n) -x en la hucha. Y cada vez que desee realizar una operación que requiera más de f (n) pasos, debe pagar el tiempo adicional con las monedas que ahorró anteriormente . El número de monedas en su alcancía en un estado dado se llama potencial de ese estado.
Así es como esto funcionaría para el vector. Asumiremos que almacenar un elemento en una nueva ubicación en la memoria cuesta 1 moneda, y que cuando el vector cambia de tamaño, el nuevo tamaño es dos veces el tamaño anterior. Ahora, la afirmación es que la complejidad del tiempo amortizado de n llamadas a push_back para un vector inicialmente vacío es de 3 monedas por push_back. Para probar este reclamo, tenemos que demostrar que el saldo en nuestra alcancía nunca será negativo.
¿Por qué es eso cierto? Considere cualquier momento que sea inmediatamente después de un cambio de tamaño. Ahora tenemos k elementos en la memoria y un espacio vacío para k más elementos. Con cada uno de los próximos k elementos obtenemos 3 monedas, pero solo gastamos 1 en colocar el elemento en un espacio vacío. Por lo tanto, cuando volvamos a llenar el vector, tendremos 2k monedas guardadas en nuestra alcancía, que es suficiente para pagar por mover esos 2k elementos a su nueva ubicación una vez que cambiemos el tamaño del vector nuevamente.
Ahora lo mismo usando el método potencial. Supongamos que hay k elementos insertados desde el último cambio de tamaño. Entonces, el potencial del estado actual (el número de monedas en el banco) es de 2k. Tenga en cuenta que puede calcular k directamente mirando el estado actual del vector (es decir, la capacidad asignada y el número actual de elementos).
Ahora podemos hacer las siguientes observaciones:
- Este potencial nunca se vuelve negativo (como se muestra arriba).
- En cada paso, si el potencial aumenta, aumenta a lo sumo 2 y la operación se ejecuta en tiempo constante.
- Si el potencial disminuye, el tiempo de ejecución es lineal en la cantidad de potencial perdido.
De la observación 2 se deduce que la cantidad total de aumentos es lineal en el número de operaciones. De la observación 1, la cantidad total de disminuciones también debe ser lineal. Y de la observación 3 se deduce que también la complejidad del tiempo total es lineal.
Dicho esto, no soy un gran admirador del método contable / potencial. En mi experiencia, otros métodos suelen ser más claros y / o más intuitivos. Por ejemplo, en el ejemplo anterior del método de contabilidad existe la constante “3 monedas” que aparece mágicamente de la nada. El 3 realmente importa, menos de 3 no funcionarían. ¿Cómo se me ocurrió?
De hecho, utilicé un método diferente: acabo de sumar directamente los movimientos de todos los elementos. Cada elemento se almacena en la memoria una vez, es decir n. Como máximo, todos los elementos se mueven en el último cambio de tamaño, es decir, como máximo n. Como máximo, n / 2 elementos se mueven en el cambio de tamaño anterior, como máximo n / 4 en el anterior, y así sucesivamente. Por lo tanto, el número total de veces que un elemento se almacena en algún lugar de la memoria es n + n + n / 2 + n / 4 + … <= 3n.
En mi experiencia, el método de contabilidad y el método potencial solo son útiles como formas elegantes de presentar la prueba.
