[Algorithm] 알고리즘 기본(2) - Basic Arithmetic

🤔 Basic Arithmethic

덧셈, 뺄셈, 곱셈, 나눗셈 즉 기본연산(사칙연산)을 Basic Arithmethic이라고 합니다.

n-bit를 가지고 있는 기본적인 bit 연산에 대해 알아보도록 하겠습니다.

 

 

이전에 모든 계산에 있어 단일 bit에 대해 기본적인 bit 연산에 $O(1)$시간이 소모된다고 가정하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

🔎 두 n-bit 이진수의 덧셈

$53$과 $35$의 이진수인 "1 1 0 1 0 1"과 "1 0 0 0 1 1"을 예시로 더해보겠습니다.

 

 

 

위와 같이 6bit 연산에서 최상위 비트에서의 Carry가 발생하여 7bit가 결과값으로 출력되었습니다.

 

 

두 개의 n-bit 짜리 이진수가 주어졌을 때 n 번의 덧셈이 반복되면서 일어나는 것을 알 수 있습니다.

즉 두 n-bit 이진수의 덧셈의 시간복잡도는 $O(n)$인 것을 알 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

🔎 두 n-bit 이진수의 곱셈(Algorithm 1)

$13$과 $11$의 이진수인 "1 1 0 1"과 "1 0 1 1"을 예시로 곱해보겠습니다.

 

 

 

 

 

 

 

위의 식을 봤을때 두 4bit 이진수의 곱셈인 것을 알 수 있습니다.

이때 "1 0 1 1"의 각 비트를 "1 1 0 1"과 AND연산을 통해 진행된 뒤 각 자릿수 만큼인 3 번의 Shift가 일어난 것을 알 수 있습니다.

이후 4개의 중간값을 더하기 위해 3번의 덧셈연산이 진행됩니다.

해당 값들을 모두 더했을때 8bit인 "1 0 0 0 1 1 1 1"이 출력된 것을 알 수 있습니다.

자릿수의 이동과 Carry를 고려했을때 최대 두 배의 bit자리의 결과값이 출력된다는 것을 추측할 수 있습니다.

 

 

두 n-bit 이진수를 $x$와 $y$로 일반화하여 시간복잡도를 분석해보겠습니다.

이때 고려해야할 것은 1) Shift연산과 2) 덧셈연산의 횟수입니다

 

 

 

1) $y$의 각 bit에 대해 최대 n-1 번 shift 연산이 진행됩니다.

2) 최대 2n-bit로 이루어진 이진수가 n-1번의 덧셈연산이 진행됩니다.

 

 

 

Shift연산이 총 n-1번까지 일어나므로 이는 $$O(1) + O(2) + ... + O(n-1) = O(n^2)$$

라고 나타낼 수 있습니다.

 

 

 

앞에서와 같이 두 n-bit 이진수의 덧셈의 시간복잡도는 $O(n)$입니다.

덧셈 연산을 총 n-1번 반복해야 하므로 이는 $$O(n) * (n - 1) = O(n^2)$$

라고 나타낼 수 있습니다.

 

 

 

Shift연산과 덧셈 연산의 시간복잡도를 더하더라도 $O(n^2)$에 비례하다고 할 수 있기 때문에

$x$와 $y$의 곱셈의 시간 복잡도는 $O(n^2)$입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎  두 n-bit 이진수의 곱셈(Algorithm 2)

두 수 $x$와 $y$를 곱합다고 했을 때 아래의 방법을 적용합니다.

 

 

 

1. 집합 $S=∅$ 로 둡니다.

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$ 에 속한 순서쌍의 왼쪽에 있는 숫자들을 모두 더해줍니다.

 

 

이해를 돕기 위해 아래의 예시를 살펴보겠습니다.

 

 

 

 

 

 

해당 과정을 Pseudocode로 작성하면 아래와 같습니다.

 

function multiply(x, y)

if(y == 0): return 0
z = multiply(x, y / 2)

if (y % 2 == 0): return 2*z
else: return x + 2z

 

 

위의 알고리즘을 증명하기 위해 수학적 귀납법을 사용하겠습니다.

 

 

 

 

 

 

 

 

 

 

🔎 Multiplication 의 시간복잡도

function multiply(x, y)

if(y == 0): return 0
z = multiply(x, y / 2)

if (y % 2 == 0): return 2*z
else: return x + 2z

 

 

위의 코드를 분석하겠습니다.

 

n-bit 이진수인 y를 2로 나눈다 즉 right shift 하는 작업을 1번, 전체에 2를 곱한다 즉 left shift하는 작업을 1번씩 수행함을 알 수 있습니다.

각각의 작업에는 $O(1)$의 시간복잡도를 가지며 

 

위의 코드를 해석하면 $O(n)$의 작업을 최대 $n$회 호출하기 때문에 시간복잡도는 $O(n^2)$이라고 할 수 있습니다.