시간 복잡도 이해하기

 

 

코딩테스트 준비를 하면서 시간 복잡도에 대한 이해를 빼놓을 수가 없기에 정리해본다. 

 

시간 복잡도란?

 

입력크기 n이 변화함에 따라 연산 횟수의 증가 추세를 보는 기준 

시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 

 

시간 복잡도 시각화출처 : https://levelup.gitconnected.com/big-o-time-complexity-what-it-is-and-why-it-matters-for-your-code-6c08dd97ad59

 

1. O(1) — 상수 시간

int x = 1; 
int y = 2; 

System.out.println(x+y);

입력 크기랑 상관없이 항상 1번만 실행되므로 O(1) 로 표현할 수 있다.

 

2. O(n) - 선형

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

n 이 커질 수록 for문의 반복 횟수가 늘어나므로 O(n) 로 표현할 수 있다.

 

3. O(n²) — 이중 반복문 

for(int i =0; i< n; i++){
	for(int j =0; j<n; j++){
    	...
    }
}

 중첩 for문을 사용하여 n*n 만큼 실행되므로 시간 복잡도는 O(n²) 로 표현할 수 있다.

(⚠️ 가장 최악)

 

4. O(log n) — 로그

while(n >1){
	n/=2;
}

탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 이진 탐색을 예로 들 수 있다. 

반씩 줄어드므로 n이 커져도 거의 느려지지 않는다. 

 

5. O(n log n)

Arrays.sort(arr);

 

 

 

우선 기준을 잡고 데이터를 쪼갠다 (log n 과정) * 쪼개진 데이터에서 작업을 수행한다(n 과정) = O(n log n)

작은 그룹들을 이용해 불필요한 비교를 생략하기 때문에 n² 이 아니라 n*log n 이 된다.

 

[자료구조별 시간 복잡도]

자료구조	접근/조회(get)	검색(Contains)	추가(Add)	삭제(Remove)
Array	O(1)	O(n)	O(n)	O(n)
ArrayList	O(1)	O(n)	O(1)	O(n)
LinkedList	O(n)	O(n)	O(1)	O(1)
HashSet		O(1)	O(1)	O(1)
HashMap	O(1)	O(1)	O(1)	O(1)

 

 

 

+) HashSet 의 검색 복잡도가 O(1) 인 이유 

public class HashSet<E> {
    private transient HashMap<E, Object> map; 
    private static final Object PRESENT = new Object(); 
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null; 
    }
}

HashSet은 내부적으로 HashMap을 가지고있으며 .add()로 값 자체가 곧 key값이 되며 검색시 map의 key 값으로 찾기 때문에
검색 시 시간 복잡도는 HashMap과 같은 O(1)이 나온다.