[알고리즘] Big-O 표기법

알고리즘의 효율 측정 방법이다. 

 

1. 수행되는 연산의 개수를 대략적으로 판단 

int sum = 0; // 1

int sum = 0;
for(int i=0;i<n;i++)
{
	sum+=i;
} //n+1

int sum = 0;
for(int i=0;i<n;i++)
{
	for(int j=0;j<n;j++)
    {
		sum+=1;
    }
} //n^2+1

 

2. 계수는 무시한다.

O(4N^2 + 3N + 1) => O(N^2)

https://www.freecodecamp.org

Big-O 표기법은 입력 N의 크기에 따라 성능이 영향 받는 정도를 나타낸다. N^2는 효율이 나빠 실전성이 없다.

log n 함수는 그래프처럼 효율이 매우 좋은데, 업다운 게임을 예시로 들 수 있다. 

맨 위가 로그 함수의 형식이고 업다운 게임을 통해 숫자 78을 찾는다고 하자. 그렇다면 처음에 N개 (100개)의 데이터가 있을 것이고 2분의 1을 곱하는 것을 계속해서 데이터를 반씩 줄여나가고 1이되면 정답이 도출된다. 그 식을 도출해보면 

로그함수의 형태를 띄는 것을 알 수 있다.