[수학과 프로그래밍] 2의 승수의 합 (등비수열의 합)

이 카테고리에서는 단순히 수학적 공식 혹은 지식을 깊게 다루진 않는다.

프로그래밍과 연관 지어서 유용하게 사용할 수 있는 수학적 지식을 다룬다. 

---

1 + 2¹ + 2¹ + 2² + ... + 2ⁿ 의 수열의 합은 무엇일까?

2의 승수의 합은 등비 수열의 합이다. 

 

등비 수열이란 일정한 비를 가지고 나열된 수열을 뜻하는데, 이 등비수열의 합의 공식은 아래와 같이 유도했다.

등비수열 Sn을 원래 순서대로 한 번, 순서를 바꿔서 한번 더해서 2로 나눈다. 

 

등비수열의 합 공식 도출 과정

 

출처 :https://mathbang.net/612

아마 고등학교 수학을 배운지 한참 지난 프로그래머 직장인이라면 해당 개념을 분명히 배웠지만 잘 기억이 나지 않을 것이고, 이런 게 있었나 싶을 것이다. 

 

그렇다면 프로그래머가 이해하기 쉽게 해당 등비 수열의 합을 이해해보자.

한 가지 훌륭한 방법은 이 값을 2진수로 생각해보는 것이다. 

 

승수	2진수	10진수
2의 0승	00001	1
2의 1승	00010	2
2의 2승	00100	4
2의 3승	01000	8
2의 4승	10000	16

2진수 부분을 더하면 ...11111₂ 이런 식으로 될 것이다.

 

따라서 1 + 2¹ + 2¹ + 2² + ... + 2ⁿ 을 2진수로 표현하면 1이 연속으로 (n+1) 개 나열된 값과 같다고 볼 수 있다. 즉

...1111111² 이런식으로 n+1개 나열되었고 이 값은 2의 (n+1)승에서 1을 뺀 값과 같다. 

 

1 + 2¹ + 2¹ + 2² + ... + 2ⁿ  = 2^(n+1) -1

 

 

 

 

 

 

 

 

 

---

1 + 2¹ + 2¹ + 2² + ... + 2ⁿ 의 수열의 합을 어떤  프로그램과 연관 지을 수 있을까? 

이 카테고리의 대부분의 수학과 프로그래밍 관련 글은 아마 프로그램의 시간복잡도를 계산하는데 유용하게 사용될 개념이다. 

 

즉, 이 2의 n승으로 이루어진 등비수열의 합 또한 시간복잡도를 계산하는 데 사용될 것이다. 

아래와 같은 코드가 주어질 때 이 프로그램의 시간복잡도는 몇일까?

int recursive(int n){
	if(n<=1) { 
    	return 1;
    }
    return recursive(n-1) + recursvie(n-1);
}

함수 recursive가 2번 호출 되었다고 O(N²)이라고 하면 완전히 틀렸다.

이 함수의 호출 구조를 생각해본다면, 

recursive(n)
-> recursive(n-1) + recursive(n-1)
-> recursive(n-2) + recursive(n-2) + recursive(n-2) + recursive(n-2) 
-> ...

이런식으로 계속 2배씩 늘어난다.

 

n이 0일때 1, n이 1일 때 2, n이 2일 때 4.. 이런 식으로 진행된다.

즉, 전체 노드의 개수는1 + 2¹ + 2¹ + 2² + ... + 2ⁿ 과 같고, 해당 함수의 시간복잡도는 O(2^(n+1) -1) = O(2ⁿ)이다. 

 

결론을 내 자면,

• 프로그래머는 수학적으로 2의 승수의 합은 해당 수열의 다음 값과 아주 유사한 값을 가진다는 것을 기억하면 된다.
• 또한 자신이 짠 코드가 재귀적으로 구성되었을 때 위와 유사한 형태로 성능이 결정이 된다는 것을 기억하고 염두하며 코드를 구성해야 한다. 

 

추가적으로 공간 복잡도를 설명하자면, 전체 노드의 개수는 O(2ⁿ) 이지만, 특정 시점에서의 사용하는 메모리 공간의 크기는 O(n) 이라고 볼 수 있다. 

 

---

그렇다면 균형 이진 탐색 트리에서 아래와 같은 모든 노드의 값을 더하는 코드의 수행 시간은 어떻게 될까? 

int sum(Node node){
	if(node == null){
    	return 0;
    }
    
    return sum(node.left) + sum(node.right) + node.value;
}

재귀적으로 구성되었고 위와 같은 비슷한 형태이기 때문에  O(2ⁿ) 일까?

답은 O(n)이다. 왜 그런지 잘 생각해보자.