C_1. 공간 복잡도 & 시간 복잡도

1. 공간 복잡도 & 시간 복잡도

1. 공간 복잡도(Space Complexity)

알고리즘 메모리 사용량에 대한 분석결과

 

2. 시간 복잡도(Time Complexity)

알고리즘 수행시간 분석결과

 

3. Big-O 표기법(Big-O Notation)

시간 복잡도에서 가장 큰 영향을 미치는 차항으로 시간복잡도를 나타내는 것

 

4. Big-O 종류

1. O(1) - 상수 시간: 입력값 n이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거침. 
2. O(log n) - 로그 시간: 입력값 n이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬, 이진탐색.
3. O(n log n) - 선형로그 시간: 퀵 정렬, 병합 정렬, 힙 정렬. 
4. O(n) - 직선적 시간: 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
5. O(n^2) - 2차 시간: 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
6. O(n^3) - 3차 시간: 문제를 해결하기 위한 단계의 수는 입력값 n의 세제곱. 
7. O(n^C) - 다차 시간. (C는 상수)
8. O(n!) - 팩토리얼 시간, 억지로 만들지 않은 한 거의 못 봄. 

 

4. 시간 복잡도 빠른 순서대로

O(1) > O(logn) > O(n) > O(nlog n) > O(n^2) > O(n^3) > O(2^n) > O(n!)