자료구조 복잡도
목차
- 복잡도
- 시간복잡도
- 공간복잡도
- 시간복잡도가 낮지만 메모리 사용량이 높은 경우 대처법
- 시간복잡도를 낮춰본 사례
1. 복잡도(Complexity)
: 알고리즘의 성능을 나타내는 지표(= 가독성)
- 불특정한 함수의 성능적인 측면에서의 복잡도를 의미함
- 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮은 알고리즘이 좋은 알고리즘
2. 시간복잡도(Time Complexity)
: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
- 특정 알고리즘이 문제상황을 해결하는데 걸리는 시간을 의미함
- 같은 결과를 가져오는 코드라면 시간 복잡도가 적을수록 더 효율적인 알고리즘
* 빅-오(Big-O) 표기법
‘worst case’를 기준으로 표기함(아무리 오래 걸려도 이것보단 오래 걸리지 않는 시간을 기준으로 알고리즘 성능 표기)
시간 복잡도 표기
- 전체 시간 순서(빠름-느림) : O(1) > O(log N) > O(N) > O(n²) > O(2ⁿ)
- O(1) - 상수 시간(Contant time) : 입력 크기(n)에 상관없이 일정한 연산을 수행하는 시간복잡도 | Ex. 스택의 push,pop
- O(log₂ n) - 로그 시간(Logarithmic time) : 입력 크기(n)이 커지면 연산 횟수가 log₂ n 에 비례해서 증가하는 시간복잡도 | Ex. for문
- O(n) - 선형 시간(Linear time) : 입력크기(n)이 커지면 연산 횟수가 n에 비례해서 증가하는 시간복잡도 | Ex. 이진트리
- O(n²) - 2차 시간(Quadratic time) : 입력크기(n)이 커지면 연산 횟수가 n²에 비례해서 증가하는 시간복잡도 | Ex. 이중for문, 삽입정렬, 거품정렬, 선택정렬
- O(2ⁿ) - 지수 시간(Expotential time) : 입력 크기(n)가 커지면 연산 횟수가 2ⁿ에 비례해서 증가하는 시간복잡도 | Ex. 피보나치 수열
3. 공간복잡도(Space Complexity)
: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
- 프로그램이 필요로 하는 메모리 공간 = 고정 공간 요구 + 가변 공간 요구
- 고정 공간 : 처리할 데이터 양에 무관하게 항상 요구되는 공간. 프로그램 성능에 큰 영향 X
- 가변 공간 : 처리할 데이터 양에 따라 다르게 요구되는 공간. 프로그램 성능에 큰 영향 O
- 시간복잡도와 유사하게 빅오 표기법을 사용함
- 공간 복잡도가 실패했을 경우 : 보통은 변수 설정에 문제가 있다고 볼 수 있음
- 공간 복잡도가 중요한 경우
- 최근 컴퓨터의 성능의 발전으로 중요성이 예전보다는 줄어들었으나 데이터를 많이 다루는 빅데이터 분야에서는 여전히 중요한 지표로 다뤄짐
- 동적 계획법(Dynamic Programming)
- 큰 문제를 작은 문제로 쪼개 그 답을 저장하고 재활용하는 경우
4. 시간복잡도가 낮지만 메모리 사용량이 높은 경우 대처법
(= 공간 복잡도 줄이는 방법)
공간 복잡도를 결정하는 것은 : 보통 배열의 크기가 몇인지, 동적할당을 한다면 얼마만큼의 동적할당이 예상되는지, 재귀함수라면 재귀호출을 몇번이나 하는지 등이 영향을 미침
- 시간적인 측면을 무시하고 공간 복잡도만 고려하는 경우 - 고정 공간보다는 가변 공간을 사용할 수 있는 자료구조들을 사용하는 것이 효율적
- 함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요하기 때문에 - 재귀함수의 경우 반복문으로도 짤 수 있을 때 → 반복문 사용이 효율적임
5. 시간복잡도를 낮춰본 사례 이미지 참고
- 반복문을 줄이자(제일 큰 영향)
- 적절한 자료구조의 사용
- 적절한 알고리즘의 이용
출처