1. 알고리즘 성능 평가의 필요성
2. 시간 복잡도(Time Complexity)
1-1. 소개
1-2. 예시
1-3. 종류
3. 공간 복잡도(Space Complexity)
알고리즘 성능 평가의 필요성
컴퓨터 프로그래밍은 데이터를 처리하고 연산하는 과정으로 이루어집니다.
프로그램의 규모가 커질수록 처리해야되는 데이터가 늘어나고 결과적으로 알고리즘의 효율성에 따라서 큰 차이가 벌어지게 됩니다.
| 입력 데이터 수(n) | 처리시간(n²) |
|---|---|
| n = 7 | 49초 |
| n = 100 | 10,000초 |
| n = 700 | 490,000초 |
시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)는 모두 알고리즘 성능을 가늠하기 위해서 사용됩니다.
시간 복잡도
- 소개
시간 복잡도(Time Complexity)는 알고리즘의 실행에 걸리는 시간을 나타내는 것이지만 절대적인 시간이 아닌 몇번의 연산이 일어나는지를 표기하는 것입니다.
복잡도를 표기할 때는 빅-오(O) 표기법을 사용하며 빅-오가 나타내는 값은 최악의 경우를 나타내는 방식입니다.
- 예시
데이터의 집합의 정렬에 따라서 최선, 평균, 최악의 케이스로 나눌 수 있습니다.
예를 들어서 배열을 순차적으로 탐색하는 연산의 경우 찾는 값이 어떤 순서에 위치했느냐에 따라서 연산의 수가 달라지게 됨으로 처리시간이 달라지게 됩니다.
| 찾는 값(Value) | 3 | 6 | 9 | 12 | 15 |
|---|---|---|---|---|---|
| 배열 순서(Index) | 0 | 1 | 2 | 3 | 4 |
위의 경우 찾는 값이 '3'이라면(최선의 경우) 연산이 한번만 일어나지만 찾는 값이 '15'라면(최악의 경우) 연산이 5번 이루지게 됩니다.
- 종류 예시
빅-오 표기법은 최악의 경우를 나타냅니다.
데이터 크기와 상관없이 성능이 일정한 알고리즘은 O(1)로 표기합니다.
1차원 for 문의 경우는 O(n)으로 데이터(n)에 따라 처리시간도 n배가 됩니다.
- O(1): 스택의 Push, Pop
- O(n): for문
- O(n²): 이중 for 문
공간 복잡도
공간 복잡도의 경우는 알고리즘 연산 시 필요한 메모리 공간의 크기에 따라 성능을 분석하는 방법입니다.
최근에는 컴퓨팅 파워가 높아짐에 따라 시간 복잡도에 비해 중요성이 떨어지고 있고 시간과 공간 복잡도는 반비례 경향을 가집니다.
공간 복잡도에 영향을 끼치는 요소로는 배열의 크기, 동적 할당 여부, 재귀함수의 횟수 등이 있습니다.
참고 사이트
해당 페이지를 참고하여 작성했습니다.
깃헙블로그
https://madplay.github.io/post/time-complexity-space-complexity
