시간 교대의 복잡성과 추가 곱셈

Question

나는 아래의 이미지를 기반으로 곱셈 알고리즘을 컴퓨터의 변화의 시간 복잡도를 파악하고 추가하는 것을 시도하고있다 작업의 각 단계는 B 시간 단위를 필요로하며 추가 단계가 항상 수행됩니다.이 알고리즘의 시간 복잡도는 O (n * n)이 될 것이며 시프트 및 추가는 O (n)이 될까요?

Answer 1

비트 연산을 계산하는 경우, n이 최소 피연산자의 비트 수이고 m이 곱의 비트 수이면 O (n * (n + m))가됩니다. (두 피연산자를 비교하고 가장 작은 것을 승수로 선택하고 루프 종료 조건은 이동 된 승수가 0 임). m = n + k (여기서, k는 피승수의 비트 수이므로, 본질적으로 O (n^2)가됩니다.

그러나 실제로는 비현실적입니다.

대부분의 CPU에서 시프트 (1 단위에 의한) 명령어와 명령어 추가는 단위 시간이 걸립니다. 따라서 단위 기계 명령어의 측면에서 복잡성을 원한다면 shift-and-add 곱셈은 O (n)입니다.