Big-O 표기법

Big-O

• 서로 다른 알고리즘의 효율을 측정, 비교하기 위한 방법
• 수행되는 연산(산술, 비교 대입) 의 개수를 '대략적으로' 판단

// 수행 횟수: 1
int Add(int n){
	return n+n;
}

// 수행 횟수: N² + 1
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;
}

• 영향력이 가장 큰 대표 항목만 남기고 삭제
• 상수는 무시한다.(2N -> N)

// 수행 횟수: N² + 1
// Big-O: O(N²)
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² + 4N + 1
// Big-O: O(N²)
int Add4(int n){
	int sum = 0;
    
    for(int i=0;i<n;i++){
    	for(int j=0;j<n;j++){
        	sum+=1;
        }
    }
    for(int i=0;i<4;i++){
    	for(int j=0;j<n;j++){
        	sum+=1;
        }
    }
    return sum;
}

• Big-O를 통해 입력 N의 크기에 따라 성능이 영향을 받는 정도를 나타낼 수 있다.

  • ex) 위와 같이 n²의 시간복잡도를 갖는 알고리즘의 경우 데이터가 많은 경우
    사용시 효율이 나쁘다.

  • ex) logN 의 시간복잡도를 갖는 이진트리 알고리즘의 경우 효율이 좋다.