알고리즘의 효율 측정
첫 글에서 알고리즘은 문제를 해결하는 것이라 했다.
종이에 문제를 푼다고 가정해보자.
1분이 걸려 푸는 것이 좋은가, 100분이 걸려 푸는 것이 좋은가?
1장의 종이를 쓰는 것이 좋은가, 100장의 종이를 쓰는 것이 좋은가?
알고리즘도 비슷한 맥락이다.
적은 시간, 적은 자원을 사용하는 알고리즘을 일반적으로 효율적인 알고리즘이라 한다.
시간 복잡도
시간 복잡도는 실행시간이란 관점에서 알고리즘의 효율을 표기하는 방법을 말한다.
보통 최선의 경우, 최악의 경우, 평균 세 가지를 나타낸다.
빅오표기법
빅오 표기법은 최악의 경우를 나타낸다.
다음은 n을 입력받아 1부터 n까지의 합을 구하는 과정을 의사코드로 나타낸 것이다.
n
result=0
i=1
while(i<=n)){
result = result + 1
i=i+1
}
print(result)
다음은 10을 입력했을 때의 수행과정이다.
n=10
result=0
i=1
while(i<=10)){
result = result + 1
i=i+1
}
print(result)
각 코드의 실행 횟수를 살펴보자
n부터 i=1까지 3줄,
반복문 안은
i=1,i=2,i=3,i=4……i=10일 때 실행되며
총10회 즉, n회 실행된다.
반복문 안이 2줄 이므로
총 20줄,
print(result) 1줄.
총 24줄이 실행되었다.
이번에는 입력의 크기를 늘려서 1000000000를 입력해 보자.
n부터 i=1까지 3줄,
반복문 안은
i=1,i=2,i=3,i=4……i=1000000000일 때 실행되며
총1000000000회 즉, n회 실행된다.
반복문 안이 2줄 이므로
총 20000000000줄,
print(result)
1줄.
총 20000000004줄이 실행되었다.
이때, 실행되는 줄 수를
2n+4
로 나타낼 수 있음을 알 수 있을 것이다.
이때 2n+4에 대해 살펴보자.
\(<y=2x+4,y+2x의 그래프>\)
축의 값을 키우면
\(<y=2x+4,y+2x의 그래프>\)
n이 10일때, 상수항 4는 전체의 약 13%를 차지하지만
n이 1000000000일때 상수항 4는 전체의 약 0.00000002%를 차지한다.
이를 통해 n이 커짐에 따라 상수항의 영향이 매우 작아짐을 알수 있다.
다음은 2(n+1)^2 이하의 모든 자연수의 합을 구하는 과정을 의사코드로 나타낸 것이다.
n
result
i=1
while(i<=2(n+1)^2)){
result=result+i
i=i+1
}
print(result)
위코드에서 실행되는 코드 줄 수는 \(2n^2+4n+2\) 가 됨을 알수 있다.
\(<y=2x2+4x+2, y=2x2+4x, y= 2x2의 그래프>\)
이 역시 축의 값을 키워보면
\(<y=2x^2+4x+2, y=2x^2+4x, y= 2x^2의 그래프>\)
차이가 매우 적어짐을 알 수 있다.
이러한 이유로 상수항뿐만 아니라 최고차항을 제외한 항들은 값에 큰 영향을 주지않는다.
아래 그래프도 살펴보자.
\(<2x^2 , x2 의 그래프>\)
축의 값을 키우면
\(<y=2x^2 , y=x^2 의 그래프>\)
차이가 매우 적어진다.
따라서 최고차항의 계수도 일반적으로 큰 차이를 만들어내지 않음을 알 수 있다.
위 내용들을 정리하자면 다음과 같다.
- 최고차항만
- 계수 제외
이렇게 우리는 알고리즘의 실행 코드 수를 파악 할 수 있게 되었다.
이제 그걸 O()안에 넣어주면,
O(n), O(n^2)
빅오표기법이 되었다!
수학적인 방법으로 접근해보자.
빅오 표기법의 정의는 다음과 같다.
\[두 함수 f(x) g(x)가 있을때 모든 n>n_0에 대해\\ |f(x)| <= c * |g(x)|를 만족하는 2개의 상수 C와 n0가 있으면\\ f(n) = O(g(n))\] \[f(x) = 2x^2 + 4x + 2, \\ g(x) = x^2, \\ f(x) <= 3g(x) (단,x>4) \\ 이므로 \\ f(x) = O(g(x)) = O(x2) \\ 이다.\]또한 g(x)가 상수인 경우에, \(g(x) = c*1\) 이기 때문에
O(1)
로 표기한다.
빅오메가 표기법
빅오메가 표기법은 최선의 경우를 나타낸다.
\[두 함수 f(x), g(x)가 있을 때,\\ 모든 n>n_0에 대해 |f(x)| >= c * |g(x)|를 만족하는 2개의 상수 C와 n_0가 있으면\\ f(n) = Ω(g(n))이 된다.\] \[f(x) = 2x^2 + 4x + 2, \\ g(x) = x^2, \\ f(x) >= 2*g(x) \\ 이므로 \\ f(x) = Ω(x^2) \\ 이다.\]빅세타 표기법
빅세타 표기법은 평균적인 경우를 나타낸다. \(f(x) = Ω(g(x)) \\ f(x) = O(g(x)) \\ 일때, \\ f(x) = Θ(g(x))\) 일반적인 경우에는
위 그래프와 같이 O와 Ω 사이가 Θ가 되는 것이다.
공간복잡도
공간복잡도는 알고리즘을 수행했을 때, 메모리나 저장공간이 얼마나 필요한지 나타낸 것이다.
다음 두 의사코드를 살펴보자.
function Sum(n){
if(n==1) return 1
return Sum(n-1)+1
}
n
result
i=1
while(i<=2(n+1)^2)){
result=result+i
i=i+1
}
print(result)
1,2는 모두 n이하 자연수의 합을 구하는 방법을 나타내고 있다.
1에서 컴퓨터는 1부터 n이하의 합을 모두 저장 할 것이고,
2에서는 result에 값을 모두 저장 할것이다.
따라서 공간 복잡도는
O(n), O(1)
이 된다.
이번 글에서는 복잡도에 대해 알아보았다.
“시간복잡도와 공간복잡도가 모두 작으면 좋지 않을까?”
라고 생각할 수 있지만 둘은 대체로 반비례하기 때문에 하나만을 고려하는데 보통 시간복잡도를 많이 사용한다.
또 최적의 시간은 의미가 없고, 최대 시간이 중요한 경우가 많기 때문에 빅오표기법을 가장 많이 사용한다.
이 글에서 소개한 세타, 오메가 표기법이 많이 쓰이지는 않지만, 알아두면 도움이 될 것이다.
*그래프가 이상합니다. 참고바랍니다.
출처 및 참고자료
1 : https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation
https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EB%B6%84%EC%84%9D
https://kindjm.tistory.com/71
https://madplay.github.io/post/time-complexity-space-complexity
https://vaert.tistory.com/117
https://jhoplin7259.tistory.com/59
https://ehpub.co.kr/tag/%EC%A0%90%EA%B7%BC%EC%A0%81-%ED%91%9C%EA%B8%B0%EC%97%90%EB%8A%94-%CE%B8%EC%84%B8%ED%83%80/
https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation
https://madplay.github.io/post/time-complexity-space-complexity