시간 복잡도 (Time Complexity)

시간복잡도(Time Complexity)

입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

 

알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통 시간복잡도를 의미한다.

 

코딩 테스트에서의 '시간 제한'은

작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미

 

빅오표기법(Big-O Notation)

주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법

즉 함수의 상한만을 나타낸다.

 

O(N) : 5N + 3, 2N + 10lgN, 10N

O(N^2) : N^2 + 2N + 4, 6N^2 + 20N + 10lgN

O(NlgN) : NlgN + 30N + 10, 5NlgN + 6

O(1) : 5, 16, 36

 

예를 들어  N개의 데이터가 있을 때, 모든 데이터의 값을 더한 결과를 출력하는 프로그램을 만든다고 가정하자.

합계를 저장할 변수를 선언한 뒤, 모든 데이터를 하나씩 확인하며 그 값을 합계 변수에 더해주는 식으로 알고리즘을 작성할 수 있다.

 

package kr.co.dong;

public class Sum {
	public static void main(String[] args) {
		int[] array = {3, 5, 1, 2, 4};	
        int summary = 0;
        
        for(int idx = 0; idx < array.length; idx++) {
        	summary += array[idx];
        }
        
        System.out.println(summary); // .... 15
        
        // ... idx번 만큼 반복 이때 idx를 n이라 가정
        // O(N)번 만큼 반복 ... 시간복잡도는 O(N)
	}
}

 

package kr.co.dong;

public class Sum {
	public static void main(String[] args) {
		int a = 5;
        int b = 7;
        System.out.println(a + b);
        // ... 연산 횟수는 1이다.
        // 단순히 더하기 연산이 한 번 수행되기 때문
        // 이는 상수 연산이므로 시간복잡도는 O(1)로 표현가능
	}
}

 

package kr.co.dong;

public class Sum {
	public static void main(String[] args) {
		int[] array = {3, 5, 1, 2, 4};	
        int summary = 0;
        
        for(int idx = 0; idx < array.length; idx++) {
        	for(int sidx = 0; sidx < array.length; sidx++) {
            	int temp = array[idx] * array[sidx];
                System.out.println(temp);
            }
        }
        
        
        // ... idx번 만큼 반복 이때 idx를 n이라 가정, sidx를 n이라 가정
        // O(N^2)번 만큼 반복 ... 시간복잡도는 O(N^2)
	}
}