n 비트 배열 곱셈에서 시간 복잡도

Question

두 개의 n 비트 숫자를 곱하는 배열 곱셈기를 고려하십시오. 회로의 각 게이트에 단위 지연이있는 경우 배율의 총 지연은?

1. Θ (1)
2. Θ (logn) (N)
3. Θ
4. Θ (N^2)

Answer 1

이며 원인 배열의 대각선입니다.
그래서 지연은 대략 sqrt (2) * (2n-1)입니다.
Θ (n)

Answer 2

노. n 비트 어레이 곱셈기 (nxn)에서 사용되는 게이트들의 개수는 2n-1이다. 그럼. 매 게이트 유닛 딜레이를 걸리면 후 총 지연 0 (2N-1) = 0 (N) 그 지연이있을 것이다 위에 이미지를 참조하면 선형 순서