Análisis amortizado por incremento en contador

El análisis amortizado se refiere a la determinación del tiempo de ejecución promedio para una operación secuencial (no individual). Es diferente del análisis de casos promedio porque aquí no asumimos que los datos están organizados de manera promedio (no muy mala) como lo hacemos para el análisis de casos promedio para clasificación rápida . Es decir, el análisis amortizado es el análisis del peor de los casos, pero para una secuencia de operaciones en lugar de una individual. Se aplica al método que consiste en la secuencia de operaciones, donde la gran mayoría de las operaciones son baratas pero algunas de las operaciones son costosas. Esto se puede visualizar con la ayuda del contador binario que se implementa a continuación.

Veamos esto implementando un contador de incrementos en C. Primero, veamos cómo funciona el contador de incrementos. 
Deje que una variable i contenga un valor 0 y realizamos i++ muchas veces. Dado que en el hardware, cada operación se realiza en forma binaria. Deje el número binario almacenado en 8 bits. Entonces, el valor es 00000000. Incrementemos muchas veces. Entonces, el patrón que encontramos es:
00000000, 00000001, 00000010, 00000011, 00000100, 00000101, 00000110, 00000111, 00001000 y así sucesivamente…

Pasos:  
1. Iterar desde el extremo derecho y convertir todos los uno en cero hasta encontrar el primer cero. 
2. Después de la iteración, si el índice es mayor o igual a cero, entonces haga que cero se encuentre en esa posición a uno.

#include <bits / stdc++.h>
using namespace std;
 
int main()
{
    char str[] = "10010111";
    int length = strlen(str);
    int i = length - 1;
    while (str[i] == '1') {
        str[i] = '0';
        i--;
    }
    if (i >= 0)
        str[i] = '1';
    printf("% s", str);
}

import java.util.*;
 
class GFG{
 
public static void main(String args[])
{
    String st = "10010111";
    char[] str = st.toCharArray();
    int lengthh = st.length();
    int i = lengthh - 1;
     
    while (str[i] == '1')
    {
        str[i] = '0';
        i--;
    }
     
    if (i >= 0)
        str[i] = '1';
         
     System.out.print( str);
}
}
 
// This code is contributed by sanjoy_62

using System;
 
public class GFG{
 
public static void Main(String []args)
{
    String st = "10010111";
    char[] str = st.ToCharArray();
    int lengthh = st.Length;
    int i = lengthh - 1;
     
    while (str[i] == '1')
    {
        str[i] = '0';
        i--;
    }
     
    if (i >= 0)
        str[i] = '1';
         
     Console.Write( str);
}
}
 
// This code is contributed by Rajput-Ji

Producción: 

10011000

Con una simple mirada al programa o algoritmo, su costo de ejecución parece proporcional a la cantidad de bits, pero en realidad no es proporcional a una cantidad de bits. ¡Veamos cómo!

Supongamos que la operación de incremento se realiza k tiempo. Vemos que en cada incremento, su bit más a la derecha se voltea. Entonces, el número de volteos para LSB es k. Porque, el segundo más a la derecha se voltea después de un espacio, es decir, 1 vez en 2 incrementos. El tercero más a la derecha: 1 vez en 4 incrementos. 4º más a la derecha: 1 vez en incrementos de 8. Entonces, el número de cambios es k/2 para el segundo bit más a la derecha, k/4 para el tercer bit más a la derecha, k/8 para el cuarto bit más a la derecha y así sucesivamente…

El costo total será el número total de volteos, es decir, 
C(k) = k + k/2 + k/4 + k/8 + k/16 + …… que es la serie de progresión geométrica y también, 
C(k) < k + k/2 + k/4 + k/8 + k/16 + k/32 + …… hasta el infinito 
Así, C(k) < k/(1-1/2) 
y así, C(k ) < 2k 
Entonces, C(k)/k < 2 
Por lo tanto, encontramos que el costo promedio para incrementar un contador por una vez es constante y no depende del número de bits. Concluimos que el incremento de un contador es una operación de costo constante.

Referencias : 

1. http://www.cs.cornell.edu/courses/cs3110/2013sp/supplemental/recitations/rec21.html
2. http://faculty.cs.tamu.edu/klappi/csce411-s17/csce411-amortized3.pdf