시간복잡도(Time Complexity)와 Big-O

알고리즘의 성능은 대체 어떻게 측정할 수 있을까?

'시간복잡도'라는 것이 있다.

우선 의미를 알아보자.

 

시간복잡도란 특정 알고리즘이 작업을 완료하는데 걸리는 시간을 정량화하는 것이다.
-위키백과 참조-

 

시간을 정량화 한다? 이해가 갈듯말듯 하다.

쉽게 말하자면 시간복잡도는 어떠한 알고리즘이 완료되기까지 필요한 스텝을 의미한다. 즉, 분/초를 세는 것이 아닌 몇번의 단계가 필요한지를 측정하는 것이다.

 

그리고 그 단계들을 분류하기 쉽게 지표화 한 것이 'BigO Notation'이다.

 

BigO의 시간복잡도 그래프

1) O(1)

-Input사이즈에 관계없이 알고리즘이 완료되기까지 걸리는 스텝이 하나(=항상 일정)

-최적의 알고리즘(=가장 선호되는 알고리즘)

-구현하기 쉽지 않음

public void sayHello(){
	System.out.println("Hello");
}

 

2) O(log N)

-알고리즘 완료까지 걸리는 스텝이 매 연산마다 특정 요인에 의해 줄어듦

-Binary Search

public int binarySearch(int answer, int smallNum, int bigNum) {
    int middleNum;

    if(smallNum <= bigNum) {
        middleNum = (smallNum + bigNum) / 2;

        if(answer == arr[middleNum]) {
            return middleNum;
        } else if(answer < arr[middleNum]){
            return binarySearch(answer, smallNum, middleNum-1);
        } else {
            return binarySearch(answer, middleNum+1, bigNum);
        }
    }
    return -1;
}

 

3) O(N)

-알고리즘 완료까지 걸리는 스텝이 input의 사이즈와 동일

-Linear Search

public void printNumber(number){
    for(int i=1; i<=number; i++){
        System.out.println("i=" + number);
    }
}

 

4) O(N^2)

-알고리즘 완료까지 걸리는 스텝이 input사이즈의 제곱

public void printNumberSquared(number){
    for(int i=1; i<=number; i++){
        for(int j=1; j<=number; j++){
		System.out.println("i=" + n + ", j=" + j);
        }
    }
}