시간 복잡도, 공간 복잡도

공간 복잡도

• 프로그램을 실행시켰을 때 필요로 하는 자원(메모리) 공간의 양

• 총 필요 저장 공간

  • 고정 공간(알고리즘과 관계 없는 공간): 코드 저장공간, 단순 변수 및 상수

  • 가변 공간(알고리즘의 실행과 관련 있는 공간): 실행 중 동적으로 필요한 공간

• 공간 복잡도는 컴퓨터 저장공간의 기술 발달로 시간복잡도에 비해 상대적으로 중요하지 않음.

시간 복잡도

• 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간

• 문제를 해결할 때 성능, 시간에 많은 영향을 주는 부분에 대해 시간 예측

• 효율적인 코드로 개선하는 데 쓰이는 척도

시간 복잡도 표기법 - 빅오 표기법

빅오 표기법

알고리즘의 수행 시간을 대략적으로 나타내는 방법으로,

알고리즘 성능이 최악인 경우를 나타낼 때 사용한다.

1. O(1) 상수 복잡도

• 데이터양과 상관없이 항상 일정한 연산량을 갖는 알고리즘으로 가장 효율적인 규모

• 알고리즘이 완료될 때까지 필요한 단계가 일정하므로 데이터가 아무리 커지더라도
  알고리즘의 실행 시간이 변하지 않는다.

2.O(log n) 로그 복잡도

• 반으로 쪼개가며 탐색하는 알고리즘으로 이진 탐색에서 볼 수 있음

• 데이터의 로그에 비례해 알고리즘의 단계가 늘어날 때, 알고리즘이 로그 시간으로 실행

• 데이터가 커짐에 따라 알고리즘의 실행에 필요한 단계가 천천히 늘어난다.

3.O(n) 선형 복잡도

• 데이터양(n)과 비례해 연산량도 증가하는 알고리즘

4.O(n log n) 선형 로그 복잡도

• 로그 시간 복잡도와 선형 시간 복잡도를 곱한 만큼 커진다.

• 로그 시간으로 실행되는 알고리즘 O(log n)을 n번 반복하는 형태로 O(n log n)

• 데이터를 작은 부분으로 나누고 이들을 독립적으로 처리하는 형태

ex) 배열의 모든 요소에 대해 로그 스케일의 연산을 수행

5.O( n²) 2차 복잡도

• 데이터 양이 증가할수록 데이터양의 제곱만틈 연산량이 증가하는 알고리즘

6.O(2^n) 지수 복잡도

지수 복잡도는 매 단계마다 연산의 수가 두배씩 증가한다.

ex) 피보나치 수열의 재귀적 계산

참고 : 한빛출판 네트워크