시간복잡도와 빅오(Big-O)표기법

■ 시간복잡도란? 
- 문제를 해결하는데 걸리는 시간과 입력의 함수 관계로 쉽게 예를 들어, 어떤 일처리를 하는데 여러가지 방법이 있을텐데 그 중에 가능한 시간이 적게 걸리는 다시말해 시간복잡도가 낮은 일처리가 좋은 일처리라고 판단할 수 있다. 

그 중, 빅오(Big-O)표기법을 주로 사용한다.

 

■ 시간복잡도 표기법

- 최상의 경우 : 오메가 표기법(Big-Ω Notation)

- 최악의 경우 : 빅오 표기법(Big-O Notation)

- 평균의 경우 : 세타 표기법(Big-θ Notation)

 

■ 빅오 표기법

- O(1)
- O(n)
- O(log n)
- O(n^2)
- O(2n)

 

■ O(1)

O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

public class complexity {

	public static void main(String[] args) {
		int[] arr = {1,2,3,4};
		System.out.println(big_o_1(arr,3));
		

	}
	public static int big_o_1(int[] a, int b) {
		
		return a[b];
		
	}

}

이 알고리즘에선 입력값의 크기가 아무리커져도 즉시 출력값을 얻어낼 수 있다.

예를들어 arr의 길이가 커도 즉시 리턴값을 반환할 수 있다.

 

■ O(n)

입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
예를들어 입력값이 1개일 때 10초 걸리면, 2개일 대 20초가 걸리는 알고리즘

public class complexity {

	public static void main(String[] args) {
		int[] arr = {1,2,3,4};
		for(int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
			
		}

	}

}

O(n) n앞에 붙는 상수 계수 ex) O(2n), O(3n) ... 은 모두 O(n)으로 표기한다.

 

■O(n^2)

입력값이 증가함에 따라 시간이 제곱으로 증가하는 것을 의미한다.

이중포문이 O(n^2)시간복잡도를 갖는다.