빅 오 분석법 O(n)
자신이 푼 코드의 시간효율과 공간복잡도에 대해서도 명확히 말할 수 있는 개발자가 진정한 개발자라고 생각한다.
그런 의미에서는 시간 효율과 같은 경우에 대충 for문으로 때려 잡고 있던(사실 대개 반복문이 시간분석의 핵심이긴하다)
나에게는 간단하지만, 정확하게 분석 할 수 있는 능력이 필요하다고 생각한다.
빅 오 분석법
"입력 값에 따라 무엇을 n으로 놓을지 결정하고 나면 n개의 입력된 값을 몇 번이나 확인해봐야 하는지를 n의 식으로 표현"
여기서 확인하다??라는 것이 무엇인지 애매하다.
일반적으로 입력된 값에 상수를 더한다거나 새로운 입력 아이템을 만든다거나 입력 값을 삭제한다거나 비교한다던가 하는 것을 "확인" 이라고 표현 할 수 있겠다.
하나의 간단한 코드를 보면서 빅 오 분석법을 이해해보고자 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | int findMax(int arr[], int n){ /* 예외 처리 */ if (n < 1) return -1; /* 비교 할 수 */ int maxvalue = arr[0]; /* 2번째 수 부터 끝까지 최대값과 비교해서 계속 갱신해준다.*/ for (int i = 1; i < n; i++){ if (maxvalue < arr[i]) maxvalue = arr[i]; } return maxvalue; } | cs |
위의 코드는 주어진 배열에서 최대값을 찾는 코드이다. 여러 방법이 있겠지만 그 중에 위의 코드는
최대값을 찾는 변수를 할당해 놓고 모든 수와 한 번씩만 비교해서 가장 큰 값을 반환하는 코드이다.
자, 입력된 항목의 자료들이 한 번 씩만 비교하면 되므로 O(n)의 시간복잡도가 계산된다.
명확히 말하면 맨 처음에 자료가 0개인지 아닌지를 판별하는데 1이 소모 되었고,
maxvalue를 첫번째 원소로 초기화하는데 1이 소모 되었으므로
O(n + 2)라고 할 수 있다. 하지만 2라는 상수는 충분히 커진 수에서는 별로 의미가 없다.
우리는 위의 코드처럼 고작 6개의 수가 얼마나 시간이 걸리는지를 계산할려고 시간복잡도를 구하는 것이 아니기
때문이다. 우리는 수백, 수억개의 숫자들 중에서 최대값을 찾는데 걸리는 시간에 대한 복잡도를 구하는 것이다.
예를 들어 O(10000000000000 + 2)에서 2는 의미가 있나? 없다고 판단해도 된다.
그래서 시간 복잡도는 O(n)으로 계산되는 것이다.
이중 for문에서도 비슷하게 계산 가능하다.
상수 시간이 걸리는 부분은 과감히 생략되고 실질적으로 n개의 자료들이 이중 for문의 연산이 수행되면
O(n^2)이 된다. (블로그에 제곱 표기가 좋지 않아 이렇게 표현한다)
* 시간 복잡도를 구하는 방법 정리
1. 빅-오(Big-Oh)표기법
최악의 경우를 복잡도를 구하는 경우를 말한다. "최악의 경우 시간 복잡도는 O(n)이다" 이런식
2. 빅-오메가(Big-Omega) 표기법
빅 오와 반대되는 개념. 최선의 경우의 복잡도를 구하는 것을 말한다. "최선의 경우 Ω(n)이다."이런식
3. 세타(Theta) 표기법
빅오와 빅오메가의 중간인 평균적인 복잡도를 구하는 경우를 말한다.
'알고리즘' 카테고리의 다른 글
| 버블정렬 (0) | 2015.09.26 |
|---|---|
| 재귀호출 - Recursive Call (0) | 2015.09.24 |
| 조합알고리즘의 최적화 (0) | 2015.04.30 |
| 2차원 배열의 경우의 수 구하기 (0) | 2015.04.28 |
| 증가하는부분수열(Longest Increase Subsequence) (0) | 2015.04.26 |
