시간복잡도

알고리즘 복잡도란?

어느 알고리즘이 더 효율적인지를 분석하기 위한 기준

알고리즘 복잡도 종류

1. 시간복잡도

• 알고리즘의 실행 속도를 의미한다.
• 반복문이 중요하게 작용한다.

2. 공간복잡도

• 알고리즘이 사용하는 메모리의 사이즈를 의미한다.
• 메모리의 발달로 공간복잡도에 중요도가 시간복잡도에 의해서 줄어들고 있다.

알고리즘의 성능 표기법

1. Big-O (빅-오) 표기법 : O(N)

• 알고리즘의 최악의 실행시간을 표기
• 일반적으로 사용하는 표기법

2. $\Omega$ 표기법 : $\Omega$(N)

• 알고리즘의 최상의 실행시간을 표기

3. $\Theta$ 표기법 : $\Theta$(N)

• 알고리즘의 평균 실행시간을 표기

Big-O 표기법

1. O(입력)
   • 입력 n에 따라 결정되는 시간복잡도 함수
   • $O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)$
     으로 입력 n의 크기에 따라 기하급수적으로 시간복잡도가 증가될 수 있다.
   • 알고리즘 구현 시 Big-O 표기법에 의한 시간복잡도를 계산하는 습관을 길러야한다.

• $O(1)$

if(n > 10) {
	System.out.println(n);
}

• $O(n)$

for(int num = 0; num < 3; num++) {
	for(int idx = 0; idx < n; idx++) {
    	System.out.println(idx);
    }
}

• $O(n^2)$

for(int i = 0; i < 3; i++) {
    for(int j = 0; j < n; j++) {
		for(int idx = 0; idx < n; idx++) {
			System.out.println(idx);
		}
	}
}