[ Do it! 알고리즘 코딩테스트 with JAVA ] - 시간복잡도

 

 

[시간복잡도]

-> 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.

일반적으로 수행 시간은 1억번의 연산을 1초의 시간으로 간주하여 예측한다

 

[시간복잡도 유형]

* 빅-오메가 : 최선일 때(best case)의 연산 횟수를 나타낸 표기법

* 빅- 세타 : 보통일 때(average case)의 연산 횟수를 나타낸 표기법

* 빅 - 오: 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

예제

- 0~99사이의 무작윗값을 찾아 출력하는 코드

빅- 오메가 표기법의 시간복잡도는 1번 , 빅-세타 표기법의 시간 복잡도는 2/N 번 , 빅 - 오 표기법의 시간 복잡도는 N번이다

 

public class timeComplexityEx {
	public static void main(String[] args){
    	// 1~100 사이의 랜덤 값 선택
        int findNum = (int)(Math.random() * 100); //여기서 N = 100
        for(int i=0; i<100;i++){
        	if(i==findNum){
            	System.out.println(i);
                break;
            }
        }
    }
}

여기서 N= 100이고,

평균적으로 50번만에 문제를 해결 가능 -> 빅-세타는 N/2 

99번째까지 값을 찾지 못하고, 마지막에서야 값을 찾는 경우(최악의 경우) -> 빅 오는 N (100)

 

실제로 코딩테스트를 할 때에는 3가지 유형 중 빅-오(최악의 경우)를 생각해야한다!

-> 코딩테스트의 test set은 input이 여러 케이스가 있기 때문에 항상 가장 최악의 경우를 염두해두어야한다

 

 

예를 들어

logN 의 시간복잡도를 가진 연산은

100번 이 필요하다고 할 때 ... 2^6 = 64, 2^7 = 128, 즉 7번 만에 값을 찾을 수 있다

 

 

[시간복잡도 활용하기]

 

 

예) N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오

 

- 입력: 1번째 줄에 수의 개수 N(1 <= N <= 1,000,000), 2번째 줄부터는 N개의 줄에 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다(시간제한 2)

 

-> 테스트 케이스의 숫자범위가 작을지라도, 백만까지의 수를 염두해두고 풀어야한다

 

시간제한이 2초이므로, 이 조건을 만족하려면 2억번 이하의 연산 횟수로 문제를 해결해야한다

따라서 문제에서 주어진 시간 제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야 할 것인지르 판단할 수 있다

 

(연산 횟수는 1초에 1억번 연산하는 것을 기준으로 생각하기, 시간 복잡도는 항상 최악일때,= 데이터의 크기가 가장 클 때를 기준으로 합니다)

 

- 연산횟수 계산 방법

    연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기

 

- 알고리즘 적합성 평가

  * 버블 정렬(N^2) = (1,000,000)^2 = 1,000,000,000,000 > 2,000,000,000  => 부적합 알고리즘

  * 병합 정렬(NlogN) = 1,000,000 log(1,000,000) = 약 6,000,000 < 200,000,000 => 적합 알고리즘

 

 

 

[시간 복잡도 도출 고려사항 ]

1. 상수는 시간 복잡도 계산에서 제외한다

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다

 

- 연산 횟수가 N인 경우

public class 시간복잡도_판별원리1 {
	public static void main(String){
    	int N = 100000;
        int count =0;
        for(int i=0; i<N; i++){
        	System.out.println("연산 횟수:", cnt++);
        }
    }
}

-> 이 코드의 시간복잡도는 O(N)

 

    public static void main(String[] args){
        int N  = 100000;
        int count =0;

        for(int i=0; i<N; i++){
            System.out.println("연산 횟수: "+ count++);
        }
        for(int i=0; i<N; i++){
            System.out.println("연산 횟수: "+ count++);
        }
        for(int i=0; i<N; i++){
            System.out.println("연산 횟수: "+ count++);
        }
    }
}

-> 일차원 for문을 3번 돌림 -> 시간복잡도 O(3N) 

 

그런데 시간복잡도 상으로 O(N) 과 O(3N) 은 별로 차이가 나지 않는다!

결론적으로 시간복잡도는 O(N)으로 똑같다고 본다

 

그런데, 이중 for문의 경우 연산 횟수가 N X N => 연산 횟수가 N^2 이다

-> 시간복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이 코드에서는 이중 for문이 전체 코드의 시간 복잡도 기준이 된다. 만약 일반 for문이 10개 더 있다 하더라도 도출 원리의 기준에 따라 시간 복잡도의 변화 없이 N^2 으로 유지된다

 

이와 같이 자신이 작성한 코드의 시간 복잡도를 노출할 수 있다면, 실제 코딩테스트에서 시간 초과가 발생했을 때, 이 원리를 바탕으로 문제가 되는 코드 부분은 도출할 수 있고, 이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결할 수 있다