Complejidad temporal del sumador anticipado de acarreo

¿Cómo es la complejidad temporal del sumador O(log n) del acarreo anticipado? ¿Puede explicar en términos de retrasos en la puerta?

@RoyC, la pregunta o la respuesta no implican cómo calcular los retrasos en las puertas, no creo que sea lo mismo
@RoyC En esa respuesta, la complejidad del tiempo es O (1), ya que el acarreo siempre se produce después de 3 retrasos de puerta, independientemente del número de bits. Encontré muchos lugares donde se menciona que la complejidad de tiempo del sumador anticipado de acarreo es log n. Entonces, no entiendo por qué es O (log n) y no O (1). Entonces esta pregunta no es un duplicado y es nueva.
Estoy seguro de que estas diapositivas de PowerPoint (de la diapositiva n.° 30) responderán a su duda.
@SahilSingh Wow, eso es exactamente lo que necesitaba. Explica perfectamente a mi entera satisfacción. Gracias, pero es 2,5 años tarde. Ojalá hubiera encontrado esto mientras lo aprendía jaja

Respuestas (1)

Podríamos pensar en un sumador anticipado de acarreo como compuesto de dos "partes"

  1. La parte que calcula el acarreo de cada bit
  2. La parte que suma los bits de entrada y el acarreo para cada posición de bit

El yo o gramo ( norte ) la complejidad surge de la parte que genera el acarreo, no del circuito que agrega los bits.

Ahora bien, para la generación del norte t h bit de acarreo, necesitamos realizar un AND entre (n+1) entradas (si tiene dudas sobre el motivo, puede ver este enlace)

La complejidad del sumador se reduce a cómo realizamos esta operación AND. Si tenemos compuertas AND, cada una con un fan-in (número de entradas aceptadas) de k , entonces podemos encontrar el AND de todos los bits en ( yo o gramo k ( norte + 1 ) ) tiempo. Esto se representa en notación asintótica como Θ ( yo o gramo   norte ) .

Espero que ayude

Complejidad temporal del sumador anticipado de acarreo
RespuestasAquíPolítica de privacidad1y, 0v