시간 복잡도, 공간 복잡도

복잡도

알고리즘(어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어 내는 과정)의 성능을 판단하는 개념

 

시간 복잡도

알고리즘을 수행하는 데 걸리는 시간

시간 복잡도는 정확한 프로그램이 실행 시간을 초단위로 표기하는 것이 아니라, 

명령문의 실행 빈도수에 따라 대략적으로 소요 시간을 나타내기 위해 사용

 

시간 복잡도를 줄이는 방법

• 반복문의 숫자를 줄이기
• 조건문 줄이기, n * 조건문 숫자 만큼 되니까
• 자료구조를 적절하게 이용하기, 가장 효율적인 자료구조들을 적절히 사용한다면 시간 복잡도를 최대한 줄일 수 있음
• 알고리즘을 적절하게 이용하는기,
  • 대표적으로 이진 탐색, 정렬 알고리즘 등이 있음

Big-O 표기법

복잡도 관련 표기법

복잡도 함수의 최고차항의 차수에 O를 씌운 표기법으로 이 알고리즘이 가장 늦게 실행되는 상한을 의미한다. 유사한 개념으로 빅오메가와 빅세타가 있다.

 

알고리즘이 가장 늦게 실행될 때를 빅오(O), 가장 빨리 실행될 때를 빅오메가(Ω), 평균을 빅세타(θ)로 지칭한다. 주로 빅 오 표기법만이 사용되는 추세다(최악의 경우를 상정하고 짜는게 안전하니..)

 

O(1) (Constant)
입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타낸다.

데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다.

O(log₂ n) (Logarithmic)
입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘

이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당된다.

O(n) (Linear)
입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘

예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다. 1차원 for문이 있다.

O(n log₂ n) (Linear-Logarithmic)
데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘

예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적이다.

O(n²) (quadratic)
데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘

예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 된다.

이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직하다.

O(2ⁿ) (Exponential)
데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘

대표적으로 피보나치 수열을 재귀함수로 구하는 경우가 해당한다.

 

※ 여기서 n이란 입력되는 데이터를 의미

https://coding-factory.tistory.com/608

 

공간 복잡도

알고리즘을 수행하는 데 필요한 메모리 공간을 의미한다.

 

일반적으로 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있는데, 하드웨어의 성능이 점점 좋아지고 있기에

보통 알고리즘의 성능을 측정할 땐 공간 복잡도 보다는 시간 복잡도에 집중하는 추세다.

 

공간복잡도를 줄이는 방법

공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지,

동적할당을 한다면 얼마만큼의 동적할당이 예상되는지,

재귀함수라면 재귀호출을 몇번이나 하는지 등이 공간 복잡도에 영향을 미침

 

프로그램에 필요한 공간은 크게 두가지로 나눌 수 있음

1. 고정 공간
2. 가변 공간

• 시간적인 측면을 무시하고 공간복잡도만을 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료구조들을 사용하는것이 효율적
• 또 함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요.
  특히 재귀 함수같은 경우에는 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소 를 저장할 공간이 필요하기 때문에 만약 재귀적(Recursive)으로도 짤 수 있고 반복문으로도 짤 수 있는 상황에는 반복문으로 짜는게 더 효율적