시간 복잡도란?

문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

문제, 즉 알고리즘의 시간 복잡도는 주로 Big-O표기법을 사용하여 나타내며, 이전 포스팅에서 알아봤듯이 이 Big-O표기법은 계수와 낮은 차수의 항을 제외시켜 직관성이 높은(대략적인) 표현방법이다.

간략한 예를 들어 기본적인 시간 복잡도에 대해 알아보자.

O(1), Constant time

	public static void main(String[] args) {
		int[] arr = new int[10];
		
		System.out.println(arr[0]);
	}

이 코드에서는 input 사이즈가 10 이며 배열의 첫번째 인덱스인 0을 호출하고 있다.
여기서 시간 복잡도를 Big-O 표기법으로 표현하면 O(1)이다. input의 사이즈가 얼마이냐에 상관없이 0번 인덱스를 호출하는 것은 O(1)로 표현할 수 있다.

	public static void main(String[] args) {
		int[] arr = new int[10];
		
		System.out.println(arr[0]);
        System.out.println(arr[0]);
	}

위와 같이 코드를 수정하여도 마찬가지로 O(1)이다. 물론 두번 호출하였기 때문에 O(2)라고 생각할 수도 있지만 Big-O표기법의 기본 컨셉 자체가 '대략적인 표현'이다. 표현에 있어서 대세에 지장이 없다면 최대한 간략하게 표현하는 것이다.

O(N), Linear time

위 코드를 다음과 같이 바꾸면 어떨까?

	public static void main(String[] args) {
		int[] arr = new int[10];
		
		for(int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}

for문에 따라 순차적으로 0부터 9까지 10개의 인덱스를 탐색한다. 즉 시간 복잡도는 O(N)이 된다. 이 역시도 Big-O표기법에 따라 호출을 2번 하더라도 O(2N)이 되진 않는다.

O(N)을 그래프로 표현하면 다음과 같다. input이 증가함에 따라 시간도 비례하여 늘어나는 것을 알 수 있다.

O(N^2), quadratic time

2차 시간의 알고리즘이라고 할 수 있다.

	public static void main(String[] args) {
		int[][] arr = new int[10][10];
		
		for(int i = 0; i < arr.length; i++) {
			for(int j = 0; j < arr[i].length; j++) {
				System.out.println(arr[i][j]);
			}
		}
	}

2차 시간은 중첩 반복이 있을 때 발생한다.