컴퓨터 관점에서 본 합집합 매커니즘 vs 조건부 매커니즘

최근 전공수업인 응용확률론에서 흥미로운 이야기를 들었다. 컴퓨터에 계산을 시키는 데에도 코드를 어떻게 짜느냐에 따라 계산 속도가 현저히 달라질 수 있다고. 물론 당연한 소리겠지만, 지루한 수학문제 풀이 시간에 다른 주제에 대한 이야기는 가뭄에 단비같은 이야기였다. 

 

컴퓨터에게 같은 문제를 풀게 시키는데도, 연산량에서 유의미한 차이를 내며 결국 계산 수행시간이 서로 100배 이상 차이가 난다고 한다면 믿겨지겠는가? 본인은 SQL 튜닝이나 알고리즘을 배우면서 몇몇 비슷한 경험을 했던 바 있기 때문에 의심없이 믿겠지만, 일반적인 시선으로 봤을 때는 "수학문제 푸는것도 힘들어 죽겠는데, 이게 또 뭔 귀신 씨나락 까먹는 소리인가" 하는 의문이 들 수도 있을 것이다. 하지만 교수님께서는 두 풀이 매커니즘을 R 코드로 직접 만들어 오셨고, 연산속도의 차이도 직접 보여주셨다. 어떤 계산법을 적용했을 때는 단 1초가 걸리지만, 다른 계산법을 적용하면 1시간이 꼬박 넘게 걸린다. 

 

교수님께서는 합집합을 이용한 계산법과, 조건부 확률을 이용한 계산법을 서로 배틀을 붙였다. 

 

 

k개의 발생 가능한 결과가 나올 수 있는 실험에서 n개의 독립시행을 진행했을 때 (n > k), 각각의 결과들이 최소 하나씩 나올 확률을 구하는 문제이다. 

 

 

 

먼저 합집합 공식을 이용했을 때의 풀이를 나타내 보았다. 붉은 선으로 밑줄 친 부분인 모든 결과가 최소 한 번 이상 나올 확률을 구하기 위해서는, 오히려 각 결과들이 한 번도 나오지 않을 때의 합집합의 값을 구하는 것이 필요하다. 이 경우 컴퓨터는 여러 E 값들의 집합을 계산을 해야 하는데, 위의 식과 같이 kC1 + kC2 + ... +kCk-1 + kCk의 형태로 컴퓨터의 연산 횟수를 간단히 나타낼 수 있다. 예를 들어 가능한 결과값이 총 5가지라면, 즉 k = 5라면, 5C1 + 5C2 + 5C3 + 5C4 + 5C5 = 5 + 10 + 10 + 5 + 1 = 31로, 컴퓨터는 총 31번의 연산을 수행하는 것을 알 수 있다. 

 

 

 

다음에는 조건부 확률을 이용해 문제를 풀었을 때의 풀이를 나타낸 것이다. 이 방식은 k번째 결과값이 나올 횟수로 경우의 수와 확률을 분리하여 계산할 수 있는데, 가령 10개의 시행 중 6가지의 결과가 모두 한 번 이상 실행될 확률을 구하기 위해서는, 9번째, 8번째, 7번째, 6번째, 그리고 5번째 시행까지 5가지의 결과가 나타나는 확률을 구해야 한다. 마찬가지로 9번째 시행까지 5가지의 결과가 나타나는 확률을 구하기 위해서는 8번째, 7번째, 6번째, 5번째, 4번째 시행까지 4가지 결과가 나타나는 확률을 알아야 하는 것이다. 결국 시행과 결과 개수의 확률값은 우리가 직접 손으로 풀어서 해결할 수 있을 정도로 간편한 정도까지 분해시켜 풀 수 있다. 

 

 

 

n = 50, 연산량	합집합	조건부
k = 5	31	225
k = 10	1023	400
k = 15	32767	525
k = 30	1.07 * 10^9	600

 

결국 연산량 수가 선형적으로 상승하는 조건부 계산법과는 달리, k의 크기에 따라 연산량이 제곱수로 상승하는 합집합은 k=5에서는 더 유리하지만, k이 조금이라도 커지면 조건부 계산법과 달리 기하급수적으로 연산량이 증가하게 된다.