시간복잡도

 

문제의 크기와 본인이 작성한 알고리즘을 보며 시간 복잡도를 대략적으로 예상할 수 있어야 한다.

여기에는 Big-O표기법을 사용한다.

 

• 아래 코드는 Big-O 표기법으로 O(N)의 시간이 걸린다.(1부터 n까지의 합을 구하는 코드.)

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

 

• 아래의 코드는 O(N^2)의 시간이 걸린다.

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

 

• 아래의 코드는 O(1)의 시간이 걸린다.

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

 

당연히도 O(1)의 시간이 걸리는 알고리즘이 가장 좋은 알고리즘이다.

항상 시간 복잡도에 주목하며 문제를 봐야한다.

 

여러가지 시간 복잡도가 있는데, 그 종류는 아래와 같다.(전부는 아님)

• O(1)
• O(lgN)
• O(N)
• O(NlgN)
• O(N^2)
• O(N^3)
• O(2^N)
• O(N!)

시간 복잡도에 가장 큰 입력 범위를 넣었을 때, 대략 1억이 1초정도가 필요하다.

즉 (대략적으로)1초가 걸리는 입력의 크기는 아래와 같다.

• O(1)
• O(lgN)
• O(N):1억
• O(NlgN):5백만
• O(N^2):1만
• O(N^3):500
• O(2^N):20
• O(N!):10

예를 들어 최대 입력이  N <= 10만  일때, 

• O(1) -> 1
• O(N) -> N이 10만이면 10만이므로: 10만/1억 -> 0.001초
• O(N^2) -> N이 10만이면 100억이므로: 100억/1억 -> 100초

 

Big-O에서 상수는 버린다.

• O(3N^2)=O(N^2)
• O(1/2N^2)=O(N^2)
• O(5)=O(1)

두 가지 항이 있을 때,변수가 같으면 큰 것만 빼고 다 버린다.

• O(N^2+N)=O(N^2)
• O(N^2+NlgN)=O(N^2)

두 가지 항이 있는 데 변수가 다르면 놔둔다.

• O(N^2+M)

 

 

 

 

 

(백준 알고리즘 기초편 강의를 보고 정리한 글)