시간 복잡도
Big - O
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
효율적인 알고리즘이란 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 말한다. 최선의 경우만 생각하여 로직을 작성하는 것보다, 최악의 경우를 고려해야 문제에 쉽게 대비할 수 있다!
- Big-O(빅-오): 시간 복잡도가 최악의 경우
- Big-Ω(빅-오메가): 최선의 경우
- Big-θ(빅-세타): 중간(평균)의 경우
🌿 O(1) constant complexity
입력값이 증가해도 시간이 늘어나지 않는다.
예) 정수를 입력하면 그에 해당하는 인덱스의 배열 요소를 반환하는 메서드
🌿 O(n) linear complexity
입력값이 따라 시간도 같은 비율로 증가한다. O(2n), O(3n)이어도 입력값이 커질수록 n 앞의 숫자가 무의미해지므로 같은 n으로 표기한다.
예) 입력값 1일 때 1초가 걸리고, 입력값이 100일 때 100초가 걸리는 경우, for문
🌿 O(log n) logarithmic complexity
BST(Binary Search Tree)에서는 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
🌿 O(n²) quadratic complexity
입력값이 증가함에 따라 시간이 n의 제곱수 비율로 증가한다
예) 입력값이 1일 때 1초가 걸리고, 입력값이 5일 때 25초가 걸리는 경우, 다중 for문
🌿 O(2^n) exponential complexity
종이를 42번 접으면 그 두께가 지구에서 달까지의 거리보다 커진다! 구현한 복잡도가 이에 해당하면 다른 접근 방식을 고민해 보자.
ex) 재귀로 구현하는 피보나치 수열
🌳 시간 제한과 데이터 크기 제한에 따른 복잡도 예측
다루는 데이터 크기가 작으면 시간 복잡도를 줄이기 위해 고민할 필요가 없다.
| 데이터 크기 제한 | 예상되는 시간 복잡도 |
| n <= 1,000,000 | O(n) or O(logn) |
| n <= 10,000 | O(n²) |
| n <= 500 | O(n³) |
탐욕 알고리즘
Greedy
선택의 순간에 앞에 보이는 최적의 상황만 쫓는다. 도출된 값이 항상 최적의 해라고 할 수 없지만, 근사해를 찾는 방법으로 타협할 수 있다.
- 탐욕적 선택 속성: 앞의 선택이 이후 선택에 영향을 주지 않을 때
- 최적 부분 구조: 문제의 최종 해결은 부분 문제에 대한 최적 문제 해결 방법으로 구성
- 선택 절차: 현재 상황에서의 최적의 해답 선택
- 적절성 검사: 선택한 해가 문제의 조건을 만족하는지 검사
- 해답 검사: 문제가 해결되었는지 검사, 그렇지 않다면 1번으로 돌아간다
대표 예시: 거스름돈 문제, MST(최소신장트리) 알고리즘, 다익스트라(Dijkstra) 알고리즘, 최대 / 최소의 경우의 수를 구할 것을 요구하는 문제들
📚 Reference
'Etc > Algorithm' 카테고리의 다른 글
| Algorithm with Math - 순열, 조합 (0) | 2022.07.30 |
|---|---|
| Implementation - Simulation, Brute-Force, Binary Search (0) | 2022.07.28 |
| Tree와 Graph | 이진 트리와 이진 탐색 트리(BST: Binary Search Tree) (0) | 2022.07.26 |
| [자료구조] 스택(Stack)과 큐(Queue) (0) | 2022.07.24 |
| 재귀(Recursive Function) (0) | 2022.07.21 |
댓글