1️⃣ Time Complexity(시간 복잡도)의 정의
- 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가르킨 것
- 더 간단하게 설명한다면 '알고리즘의 성능을 설명하는 것'이 되겠다.
- 다른 의미로는 알고리즘을 수행하기 위해 프로세스가 수행해야 하는 연산을 수치화 한것이다.
- 그럼 왜 실행시간이 아닌 연산추치로 판별하는 것일까? 이는 여러 조건(언어, HW 등)에 따라 편차가 달라지기 때문에 명령어의 실행 횟수만을 고려하는 것이다.
2️⃣ Big O 표기법
- Big O 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 하고자 하는 데 그 목적이 있다.
- Big O로 측정되는 복잡성에는 시간과 공간복잡도가 있는데 시간 복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타내며, 공간복잡도는 알고리즘이 실행될 때 사용하는 메모리의 양을 나타낸다.
3️⃣ 시간 복잡도 문제해결 단계
✔ 가장 큰 영향을 미치는 N의 단위
| 1 | O(1) | 상수 |
| 2n + 20 | O(n) | n이 가장 큰 영향을 미침 |
| 3n^2 | O(n^2) | n^2이 가장 큰 영향을 미침 |
✔ 시간 복잡도의 문제 해결 단계
| Big O | 시간 | 설명 |
| O(1) | 상수 시간 | 문제를 해결하는데 오직 한 단계만 처리 |
| O(log n) | 로그 시간 | 문제를 해결하는 데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬 |
| O(n) | 직선적 시간 | 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐 |
| O(n log n) | 좌동 | 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형 로그형) |
| O(n^2) | 2차 시간 | 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱 |
| O(C^n) | 지수 시간 | 문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 n 제곱 |