¿Cómo es la complejidad en el tiempo de llevar hacia delante el sumador O (log n)? ¿Puede explicar en términos de retrasos en la puerta?
¿Cómo es la complejidad en el tiempo de llevar hacia delante el sumador O (log n)? ¿Puede explicar en términos de retrasos en la puerta?
Podríamos pensar que un sumador con vista anticipada está compuesto de dos "partes"
La complejidad \ $ log (n) \ $ surge de la parte que genera el acarreo, no del circuito que agrega los bits.
Ahora, para la generación del bit de acarreo \ $ n ^ {th} \ $, necesitamos realizar un AND entre (n + 1) entradas (si el motivo es una duda, puede ver this link)
La complejidad del sumador se reduce a cómo realizamos esta operación AND. Si tenemos puertas AND, cada una con un fan-in (número de entradas aceptadas) de \ $ k \ $, entonces podemos encontrar el AND de todos los bits en \ $ (log_ {k} (n + 1)) \ $ tiempo. Esto se representa en notación asintótica como \ $ \ Theta (log \ n) \ $.
Espero que ayude
Lea otras preguntas en las etiquetas adder carry-look-ahead