Considere un multiplicador de array para multiplicar dos números de n bits. Si cada puerta en el circuito tiene una unidad de retardo, el retardo total del multiplicador es
(A) Θ(1)
(B) Θ(log n)
(C) Θ(n)
(D) Θ(n 2 )
Respuesta: (C)
Explicación: número de puertas utilizadas en el multiplicador de array de bits ‘n’ (n * n) = (2n – 1)
Cada puerta en el circuito tiene una unidad de retardo.
retraso total,
= 1 * (2n – 1) = O(2n – 1) = O(n)
Supongamos 2 números A y B.
Tomar,
A = A0 A1 A2 A3 B = B0 B1 B2 B3
Para multiplicar A y B tenemos que hacer,
- Multiplique A0 A1 A2 A3 con B1 necesita 1 compuerta AND
- Multiplique A0 A1 A2 A3 con B2 necesita 1 compuerta AND
- Multiplique A0 A1 A2 A3 con B3 necesita 1 compuerta AND
- Multiplique A0 A1 A2 A3 con B4 necesita 1 compuerta AND
También se requieren 3 compuertas OR para agregar términos obtenidos por compuertas AND.
Entonces, puertas totales requeridas = 4+3 = 7 que es 2N-1.
Asi que,
Time complexity = ϴ(n)
La opción (C) es correcta.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA