BIG-O 표기

알고리즘에서 시간복잡도. 문제의 크기(N)에대해서 시간을 알아볼 수 있다.

 

big O 표기법이 라고도하며 가장 안좋은 경우에 얼마나 걸리는지 예상할수 있다.

 

O(N^N), O(N^2), 0(N) 등으로 표시할수있다.

 

N은 무한대로 커지기 때문에 사소한 부분 예를들어 O(3N) 같이 상수항 같은 부분들은 무시할 수 있다 

두가지 항이있을때는 변수가 큰것만 빼고 무시한다.  O(N^2 + N) 이라면 O(N^2)만 남겨도 된다.

변수가 다르면 두변수를 사용한다. O(N+M) 

 

1부터 N 까지의 합을 구하는 여러 종류의 코드.

int sum = 0;

for(int i = 0; i <= N; i++) {
	sum += i;
}

 

이코드를 blg-O로 표기한다면 총 N의 연산이 필요하기 때문에  O(N) 이 된다.

 

int sum = 0;

for (int i = 0; i <= n; i++) {
  for (int j = 0; j <= n; j++) {
  	if( i == j)
  		sum += j;
  }
}

 

이코드를 blg-O로 표기한다면 총 N의 연산이 N번 필요하기 때문에  O(N^N) 이 된다.

 

int sum = 0;
sum = n*(n+1)/2;

 

마지막으로 이코드는 수식하나로 연산이 가능하기때문에 O(1) 이된다.

 

이렇게 표기한것을 약 몇초가 걸리는지 알아볼수있다. 보통 1억이 1초라고 한다.

 

그렇다면

O(1) => 1 (무시해도될만큼 작음)

O(N) = O(1억) => 1초

O(N^N) = O(1억^1억) => 오래걸림

 

으로 알수있다.