자료 구조 첫 주차 수업으로 자료구조의 간단한 이해와 개념들을 살펴보았다.
그 중 가장 중요해 보였던 시간 복잡도에 관하여 이해가 되지 않는 부분들이 있어 추가적인 공부가 필요하였고
그 내용들을 정리하려 한다.
Time Complexity
일단 시간 복잡도의 계산이었다.
void ex1(int n){
int a, i;
for(i=0;i<n;i++)
a=i;
}
와 같은 간단한 코드가 있다.
대입,원소 접근은 +1
반복문은 해당 반복 n 을 취하여 각각 더하면 시간 복잡도가 된다.
위 코드로 따라간다면
void ex1(int n){
int a, i; 0
for(i=0;i<n;i++) n+1 ( 반복 + 대입)
a=i; n ( 대입을 n번 반복)
}
시간 복잡도 = 2n +1 이 된다.
그렇다면 조금 더 나아가서
void ex2(int n){
int a, i, j;
for(i=0;i<n;i++)
for(j=0;j<i;j++)
a=i;
}
를 살펴보자
어렵게 생각할 필요없이 for j 문이 n의 증가만큼 반복하기 때문에
등차수열처럼 생각하고 계산해주면 쉽다.
void ex2(int n){
int a, i, j;
for(i=0;i<n;i++) n+1
for(j=0;j<i;j++) n(n+1)/2
a=i; n(n+1)/2
}
( n(n+1)/2 + n(n+1)/2 ) * n+1 = n^3+2n^2+n 이 된다.
Big - Oh
빅 오 표기법(BIg -oh) 이러한 시간복잡도를 가지고 실행시간을 표기하는것인데
그 중 가장 최악의 경우를 생각하는 표기법이다.
그렇기에 n 차수들의 앞 상수는 제거하고 상수항 역시 제거를 하는 형식으로 표기한다.
예를 들어 앞서 우리가 계산한
n^3+2n^2+n
의 경우는
O(n^3+n^2+n) 으로 나타낼 수 있다.