시간복잡도

시간 복잡도란?

: 알고리즘의 성능을 나타내는 지표. 입력 크기에 대한 연산 횟수의 상한

 

빅오 표기법

public static void main(String[] args){
	solution(6);
}

public static void solution(int n){
	int count = 0;
    
    for (int i=0; i<n; i++){
    	for (int j=0; j<n; j++){
        	count++;
        }
    ]
    
    for (int i=0; i<n; i++){
    	count++;
	}
    
    for (int i=0; i<n*2; i++){
    	count++;
    }
    
    for (int i=0; i<5; i++){
    	count++;
    }
    
    System.out.println(count);
}

위 solution() 함수는 n = x 일때, f(x) = x^2 + 3x + 5 로 표현가능 -> O(x^2)

 

시간 복잡도를 코딩 테스트에 활용하는 법

연산 횟수는 1,000 ~ 3,000만 정도로 고려해서 시간 복잡도를 생각하면 됨.

ex) 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘은 사용 X

시간 복잡도	N의 가용 범위
O(N!)	10
O(2^N)	20~25
O(N^3)	200~300
O(N^2)	3,000~5,000
O(NlogN)	100만
O(N)	1,000~2,000만
O(logN)	10억