[알고리즘] 시간 복잡도와 코딩 테스트

 

코딩 테스트에서의 시간 복잡도

• 코딩 테스트 문제에서는 프로그램 실행 시간이 특정 미만이어야 한다는 조건이 있음
• 입력 크기와 알고리즘 간의 시간 복잡도 상관관계를 어림짐작 할 수 있어야 함
• 특히 효율성을 측정하는 문제의 경우 입력 크기가 매우 큼
• 가장 복잡한 연산 과정의 최악의 경우 시간 복잡도를 파악하여, 타임아웃이 나는지를 판단하는 것이 중요하다.

 

 

빅오 표기법

• 입력 크기가 N일 경우에 대한 시간 복잡도 표기 방법
• 최선의 경우 - 빅오메가 표기법
• 최악의 경우 - 빅오 표기법
• 평균적인 경우 - 빅 세타 표기법
• 입력 크기가 N인 전체 배열을 순회하는 경우 O(N)으로 표기
  • 다음 코드는 최악의 경우 배열의 크기만큼의 연산이 이루어지므로 O(N)의 시간 복잡도가 걸린다.

public int n = [1,2,3,4,5,6,7,8,9,10];

public int search(int[] array, int target){
	for(int i = 0; i < array.length; i++){
		if(n[i] == 10){
			return i;
		}
	}
	return -1;
}

 

입력 데이터 개수에 따른 시간 복잡도

1. 프로그램 실행 시간 1초의 제한 ⇒ 시간 복잡도가 1억 미만으로 잡으면 됨
2. 제한 사항에 표기된 가장 큰 입력을 대입하여 계산했을 때의 시간 복잡도를 계산
3. 일반적인 코딩 테스트는 시간 복잡도를 Fit하게 잡지 않음.
   1. 1초의 제한이 걸려 있다면 1억보다 한참 아래 값으로 계산되는 경우가 많음
   2. 풀이가 잘못된 경우 1억보다 한참 위로 계산되는 경우가 많음
4. 시간 제한이 걸려있지 않더라도 대부분의 코드는 10초 이내에 실행되어져야 함.
5. 시간 복잡도 계산 시 가장 영향력이 큰 항만 고려하면 됨 -> 여러 알고리즘이 있을 경우 가장 복잡한 로직을 기준으로 계산하기 
   1. O(N^2 + N) = O(N^2)
   2. O(2N) = O(N)
   3. O(NM) = O(NM)
      - M이 변수인 경우 입력 크기가 크다면 함께 고려해 주어야 함

• 길이가 N이고 정수로 이루어진 배열에서 M개의 숫자 유무를 확인해야 한다면?
  • 하나의 수를 검사할 때 마다, N개의 원소가 있는 배열을 순회하는 알고리즘 사용
  • 최악의 경우 시간 복잡도는 O(N*M)이 됨
  • 만약 문제에서 1초의 제한이 걸렸다면 [N*M > 1억]이 되는 경우 해당 알고리즘을 사용할 수 없음
    • 이진 탐색을 사용하게 되면 시간 복잡도는 O((N+M)logN))이 되어 시간 복잡도를 줄일 수 있음
    • HashSet 자료구조를 이용하면 O(N+M)의 시간 복잡도로 줄일 수 있다

 

 

 

 

 

 

효율적인 문제 풀이 과정

문제 확인 → [풀이 고안 → 효율성 검증 → 풀이 작성] → 제출 → 완료

• 코드먼저 냅다 써내려가지 말자. 풀이를 고안한 후 알고리즘 효율성을 우선적으로 파악하자.

 

 

시간 복잡도 유추하기

 

시간 복잡도/N	1	10	100
O(1)	1	1	1	해시 함수, 상수 연산, 인덱스 접근 등
O(log N)	0	2	5	이진 탐색, 이진 트리 등
O(N)	1	10	100	선형 탐색, 리스트의 모든 원소 조건 비교, 선형 탐색 기반 정렬 - 버블 정렬(최선의 경우), 계수 정렬, 기수 정렬.., 선형 시간 복잡도의 그래프 알고리즘 - DFS, BFS, 연결 요소 찾기..
O(N log N)	0	20	461	분할 정복 기반 정렬 알고리즘 - 병합 정렬, 퀵 정렬(평균), 힙 정렬, 이진 트리 정렬(평균)..
O(N^2)	1	100	10000	버블 정렬(최악, 평균), 삽입 정렬(최악, 평균), 선택 정렬(최악, 평균) 리스트의 모든 원소를 두번 확인하는 중복 값을 찾는 경우 등..
O(2^N)	1	1024	10경 이상	조합
O(N!)	1	3628800	수치 표현 불가능	순열

• 이진 탐색(O(logN))
• 선형 탐색(O(N))
• 정렬(O(NlogN))
• 조합(O(2^n))
• 순열(O(N!)

ex) 제한 시간이 1초일 때 유추 가능한 알고리즘

1. 10 → O(N!) → 3628800 →순열
   1. N = 11 < 1억 < N=12
2. 20 → O(2^n) → 1,048,576 → 조합
   1. N = 26 < 1억 < N=27
3. 20 ~ 500 → O(N^3), O(N^3 log(N)) → 삼중 반복문, 행렬 곱셈..
4. 10,000 ~ → O(N logN) → 정렬..

 

 

 

정렬과 자료구조 별 시간 복잡도

 

시간 복잡도	최선	평균	최악
버블 정렬	O(n)	O(n2)	O(n2)
힙 정렬	O(n log n)	O(n log n)	O(n log n)
삽입 정렬	O(n)	O(n2)	O(n2)
합병 정렬	O(n log n)	O(n log n)	O(n log n)
퀵 정렬	O(n log n)	O(n log n)	O(n2)
선택 정렬	O(n2)	O(n2)	O(n2)
쉘 정렬	O(n)	O(n log n2)	O(n log n2)

 

	평균			최악
	탐색	삽입	삭제	탐색	삽입	삭제
배열	O(n)	O(n)	O(n)	O(n)	O(n)	O(n)
정렬된 배열	O(log n)	O(n)	O(n)	O(log n)	O(n)	O(n)
연결 리스트	O(n)	O(1)	O(1)	O(n)	O(n)	O(n)
스택	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
해시 테이블	O(1)	O(1)	O(1)	O(n)	O(n)	O(n)
이진 탐색 트리	O(log n)	O(log n)	O(log n)	O(n)	O(n)	O(n)
B-트리	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
Red-Black 트리	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)

 

 

 

 

 

 

 

https://www.bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

https://blog.chulgil.me/algorithm/

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기