[알고리즘] 곱하기(Multiplication) 알고리즘 ($O(n^2)$)

 

 

 

 

 

 

🧐 곱하기 알고리즘 성능 분석

우리가 흔히 곱하기 계산을 할 때 사용하는 방법을 통해 n-bit 이진수 곱하기 알고리즘의 시간 복잡도를 구해보도록 하겠습니다.

 

 

우선 일반적인 계산 과정은 아래와 같습니다.

 

 

곱하기의 계산에서는 곱하는 수(y)의 각 bit에 대하여, 이동 연산(주항색 화살표로 표시)을 진행하게 됩니다.

 

첫 과정에서는 0번, 두번째 과정에서는 1번, 세번째 과정에서는 2번, .... n번째 과정에서는 n-1번의 이동 연산이 필요합니다.

 

즉 이를 빅오 표기법을 통해 나타내면 다음과 같습니다.

$$O(1) + O(2) + \cdots + O(n-1) = O(n^{2})$$

 

 

이동 연산을 모두 진행한 후에는, 최대 2n bit로 이루어진 숫자 n개에 대하여 add 연산을 진행해야 합니다.

 

이때 한번의 덧셈 과정에서는 2번의 비트 연산(캐리 비트 포함)이 최대 2n번 필요합니다. ($O(n)$)

 

그리고 이러한 덧셈은 n-1 번 이루어지므로 총 시간 복잡도는 다음과 같습니다.

$$O(n) + O(n) + \cdots + O(n) = O(n^{2})$$

 

 

즉 곱셈에 필요한 총 시간 복잡도는 $O(n^{2})$ 입니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 또 다른 곱하기 알고리즘

 

이번엔 n - bit 이진수에 해당하는 두 십진수를 곱하는 알고리즘을 알아보도록 하겠습니다.

 

 

 

 

😮‍💨 두 십진수 x와 y 곱하기 

 

1. 집합 $S = \varnothing $ 로 둡니다.

 

2. $y = 0$일 경우 0을 답하고 종료합니다.

 

3. $y$ 가 홀수인 경우 순서쌍 $(x, y)$ 를 집합 $S$ 에 추가합니다.

 

4. $x$에 2를 곱하고, $y$를 2로 나눕니다. (이때 소수점 이하는 버립니다.)

이 수를 각각 $x', y'$ 이라 할 때, $y'$이 홀수인 경우 $(x', y')$ 을 $S$ 에 추가하고, $x$과 $y$를 각각 $x'$, $y'$ 으로 바꾸어줍니다.

 

5. 과정 3, 4를 $y=0$ 이 될 때까지 반복합니다.

 

6. 집합 $S$ 에 속한 순서쌍의 왼쪽에 있는 숫자들을 모두 더해줍니다.

 

 

 

 

 

이해가 안될 수도 있으니 해당 과정을 예시를 통해 진행헤 보도록 하겠습니다.

 

 

 

 

 

해당 과정은 사실 앞서 배운 방법과 완전하게 동일한 방법입니다.

 

즉 $y$가 홀수인 경우 $x$ 를 순서쌍 집합에 추가하는 것은, $y$ 의 마지막 비트가 1인 경우 $x$ 를 모두 곱해주는 과정에 해당하며,

$x$에 2를 곱하는 과정은 덧셈 연산을 위해 왼쪽으로 한 칸 이동하는 연산(마지막 비트에 0을 붙임)과 동일합니다.

 

마찬가지로 $y$ 를 2로 나누는 과정 역시 y의 비트를 우측으로 1칸 이동시키며 마지막 비트를 버리는 과정과 동일합니다.

 

 

 

 

 

 

 

위 알고리즘을 코드로 작성해 보도록 하겠습니다.

    fun multiply(x: Int, y: Int): Int {

        if ( y == 0 ) return 0

        val z = multiply(x, y / 2)  // 최대 n번 호출

        if (y % 2 == 0)
            return 2 * z

        else
            return x + 2 * z // add -> O(n)
    }

 

$O(n)$ 의 작업을 최대 $n$ 번 호출하므로, 시간 복잡도는 $O(n^{2})$ 입니다.

 

 

 

 

 

😭 왜 최대 n번 호출하는 건가요? ㅠㅠ

$y$ 는 n비트 이진수이므로, 한번의 호출마다 한 비트씩 우측으로 이동(나누기 2)하여 마지막 비트가 사라집니다.

 

따라서 $y$ 의 비트 수인 n번 만큼 함수가 호출되는 것입니다.

 

 

 

 

 

 

😭 저 코드 뭐라는지 모르겠어요 ㅠㅠ

위 코드의 알고리즘은 다음과 같은 방식으로 동작합니다.