Big-O 표기법

보통 1억 번의 연산을 하는 데에 1초가 걸린다.

문제에서 제한시간이 1초로 주어졌을 때, 최대 연산 횟수가 1억 번을 넘지 않는지 확인해야 한다.

---

1. Big-O 표기법 1단계: 수행되는 연산(산술, 비교, 대입 등)의 개수를 대략적으로 판단한다.

public int Add(int N){
	return N + N;
}

=> 대입하는 1번의 연산

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

=> N(for문) + 1(sum에 0을 대입하는 연산) 번의 연산

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

=> N²(이중 for문) + 1(sum에 0을 대입하는 연산) 번의 연산

 

2. Big-O 표기법 2단계: 대장만 남기자

규칙1) 영향력이 가장 큰 대표 항목만 남기고 삭제한다.

규칙2) 상수는 무시(ex. 2N -> N)

 

3. Big-O 표기법 크기 비교

O(1) < O(logN) < O(N) < O(NlogN) < O(N²)