티스토리 뷰
출처: 모두의 알고리즘 with 파이썬
어떤 알고리즘이 문제를 풀기 위해 해야 하는 계산이 얼마나 복잡한지 나타낸 정도를 '계산 복잡도'라고 한다. 계산 복잡도를 표현하는 방법에는 여러 가지가 있는데, 그 중 대문자 O 표기법을 가장 많이 사용한다. 이 대문자 O표기법을 '빅 오' 표기법 이라고도 부른다.
예를 들어 1부터 n까지의 자연수의 합을 구하는 문제는 1부터 n까지 덧셈 연산을 n번 하는 방법이 있을 것이고, 1과 n을 더한 후 2로 나누고 n을 곱하여 구하는 방법이 있을 것이다.
예시에서 첫 번째 알고리즘처럼 입력크기 n에 대해서 덧셈을 n번 해야 하는 문제의 계산 복잡도를 O(n)이라고 표현한다. 필요한 계산 횟수가 입력 크기에 '정비례'할 때는 O(n)이라고 표현한다.
그러면 입력 크기 n에 따라 덧셈을 두 번씩 하는 알고리즘이 있다면 O(2n)이라고 표현할까? 그렇지 않다. 이때도 마찬가지로 그냥 O(n)으로 표현한다. 대문자 O표기법은 알고리즘에서 필요한 계싼 횟수를 정확한 숫자로 표현하는 것이 아니라 입력 크기와의 관계로 표현하기 때문이다.
예를 들어 n이 10에서 20으로 2배가 될 때 2n 역시 20에서 40으로 2배가 된다. 이처럼 필요한 계산 횟수가 입력 크기 n과 '정비례'하면 모두 O(n)으로 표기한다.
두 번째 알고리즘은 입력 크기 n과 무관하게 사칙연산을 세 번해야 한다. 이때 알고리즘의 계산 복잡도는 O(1)로 표현한다. 입력의 크기 n과 필요한 계산의 횟수가 무관하다면, 즉 입력 크기가 커져도 계산 시간이 더 늘어나지 않는다면 모두 O(1)로 표기한다.
대문자 O표기법은 알고리즘의 대략적인 성능을 표기하는 방법이다. 따라서 굉장히 세밀한 계산 횟수나 소요 시간을 표현한다기보다 입력 크기 n과 필요한 계산 횟수와의 '관계'에 더 주목하는 표현이라고 기억해 두기 바란다.
O(n): 필요한 계산 횟수가 입력 크기 n과 비례
O(1): 필요한 계산 횟수가 입력 크기 n과 무관
|
계산 복잡도: 시간 복잡도와 공간 복잡도 알고리즘의 계산 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 이름에서 알 수 있듯이 시간 복잡도는 어떤 알고리즘을 수행하는 데 얼마나 오랜 시간이 걸리는지 분석하는 것이다. 마찬가지로 공간 복잡도는 어떤 알고리즘을 수행하는 데 얼마나 많은 공간(메모리/기억 장소)이 필요한지 분석하는 것이다. 앞에서 우리는 사칙연산 횟수로 계산 복잡도를 생각해 보았는데 이것은 시간 복잡도에 해당한다. 어떤 알고리즘을 수행하는 데 필요한 사칙연산의 횟수가 많아지면 결국 알고리즘 전체를 수행하는 시간이 늘어나기 때문이다. |
1-1 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for 반복문으로 만들어 보자.
| print('n이 다음과 같을 때') n=int(input()) s=0 for i in range(1,n+1): s=s+i*i print('1부터 %d까지 제곱한 값의 합은'%n) print(s) |
1-2 연습 문제 1-1 프로그램의 계산 복잡도는 O(1)과 O(n) 중 무엇일까?
O(n), 1~n을 제곱하고 그것을 각각 더했으므로 2n번 계산했다. n에 비례한다.
1-3 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 공식은 n(n+1)(2n+1)/6으로 알려져 있다. for 반복문 대신 이 공식을 이용하면 알고리즘의 계산 복잡도는 O(1)과 O(n) 중 무엇이 될까요?
계산은 n과 관계없이 다음과 같이 5번만 계산하면 되므로 O(1)이다.
n+1 -> 2n+1 -> n(n+1) -> n(n+1)(2n+1) -> n(n+1)(2n+1)/6