[알고리즘] 시간 복잡도 vs 공간 복잡도 📌

알고리즘 성능 평가

• 알고리즘의 성능을 평가하기 위해서는 '복잡도(Complexity)의 척도'를 사용한다
• 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이다
• 복잡도는 시간 복잡도와 공간 복잡도가 있다
• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
• 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

 

 

알고리즘 성능 분석의 조건

• 서로 다르 알고리즘을 비교하려면 반드시 동일한 하드웨어(Hardware)를 사용한 상태에서 알고리즘의 실행 시간을 측정해야 한다
  • 만약 알고리즘 A는 일반 개인용 컴퓨터에서 측정하고, 알고리즘 B는 슈퍼 컴퓨터에서 측정한다면 측정 결과는 객관성이 없게 된다!
• 또한 알고리즘을 측정할 때 사용하는 소프트웨어의 환경도 고려되어야 한다
  • C언어와 같은 컴파일 언어의 경우, basic과 같은 인터프리터 언어에 비해 실행 속도가 빠르다

 

 

효율적인 알고리즘이란?

• 알고리즘이 수행을 시작하여 결과가 도출될 때까지 실행에 걸리는 시간이 짧고 연산하는 컴퓨터 내의 메모리와 같은 자원을 덜 사용하는 것이 효율적이라고 할 수 있다
• 즉, 시간 및 공간 복잡도가 낮을수록 효율적인 알고리즘이다!

 

 

---

🕗 시간 복잡도 (Time Complexity)

• 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다
• 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 같은 코드라면 시간이 적게 걸릴수록 좋은 코드이다
• 시간 복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는 데 연산들이 몇 번 이루어지는 지를 숫자로 표기한다
  • 여기서 연산의 종류는 산술, 대입, 비교, 이동을 말한다
  • 이 때 연산(Operation)의 실행 횟수는 보편적으로 그 값이 변하지 않는 상수(Constant)가 아니라 입력한 데이터의 개수를 나타내는 n에 따라 변하게 된다
• 연산의 개수를 입력한 데이터의 개수, n의 함수로 나타낸 것을 시간 복잡도 함수라고 말하며, 수식으로는 T(n) 이라고 표기한다
  • 연산 횟수가 다항식으로 표현될 경우, 최고 차항을 제외한 모든 항과 최고 차항의 계수를 제외시켜 나타낸다
• 즉, 시간적인 개념보단 어떠한 알고리즘을 해결하기 위한 단계 수이다
• 시간 복잡도에는 빅오(Big-O) 표기법 개념이 등장한다
  • 빅오 표기법은 최악의 경우(worst case)를 계산하는 방식이다
  • O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ) 순으로 오른쪽으로 갈수록 효율성이 떨어진다
  • 자세한 내용은 따로 포스팅을 해서 다루도록 하겠다!

 

 

 

 

시간 복잡도 줄이는 법

• 시간 복잡도에서 반복문이 가장 시간 소모에 큰 영향을 미친다
• 따라서 반복문의 숫자를 줄일수록 시간 복잡도를 줄일 수 있다

자료구조 별 시간 복잡도

• 또 다른 방법은 자료구조를 적절히 이용하는 것이다
• 위의 표는 자료 구조에 대한 시간 복잡도이므로, 이를 참고해서 적절히 사용한다면 시간 복잡도를 줄일 수 있다

 

대표적인 배열 정렬 알고리즘의 시간 복잡도

• 또 다른 방법은 알고리즘을 적절하게 이용하는 것이다
• 대표적으로 이진 탐색, 그리디 알고리즘, 정렬 알고리즘 등이 있다
• 효율적인 알고리즘을 적절한 때 사용한다면 큰 효과를 볼 수 있다

 

 

 

 

실행 시간 예측하기

• 위로 갈수록 알고리즘이 매우 빨라지며, 아래로 갈수록 n의 값이 커지고 급격하게 알고리즘의 수행 시간이 증가한다
• 대략 컴퓨터가 1억 번의 연산을 하기 위해서는 약 1초의 시간이 필요하다
• 만약 1만번의 입력 데이터가 들어온다면, O(n)의 경우에는 0.1초, O(n²)의 경우 1만*1만=1억 이므로 대략 1초 정도의 시간이 필요하다

 

 

 

 

🎁 공간 복잡도 (Space Complexity)

• 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하는지를 분석하는 방법
• 보통 메모리 사용량 기준은 MB 단위로 제시되며, RAM 사용량과 관련이 있다
• 공간 복잡도에는 '고정 공간'과 '가변 공간'이 있는데, 공간 복잡도는 이 둘의 합인 것이다
  • 고정 공간
  • > 입출력과 관계 없는 공간
  • > 단순 변수, 상수 변수와 같이 고정적으로 정의된 변수들이 해당된다
  • 가변 공간
  • > 동적인 공간
  • > 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들이 해당된다
  • > 함수 선언에 사용된 인자들, for 문ㅇ르 위한 가상의 변수(i 또는 n) 이 차지하는 공간
• 현재에는 예전에 비해 컴퓨터의 성능이 발달하여 메모리 공간이 넉넉하다 보니 시간 복잡도에 비해 중요도가 떨어진다
  • 최근 대용량 시스템이 보편화되면서 공간 복잡도보다는 시간 복잡도가 우선이다
  • 시간 복잡도의 경우 알고리즘을 잘못 구성하면 결괏값이 나오지 않거나 너무 느리기 때문에 최근에는 시간 복잡도를 더 우선시하여 프로그래밍한다
• 시간과 공간은 반비례적인 경향이 있다
• 즉, 알고리즘은 시간 복잡도가 중심이 된다!

 

 

공간 복잡도를 줄이는 방법

• 공간 복잡도를 결정하는 것은 보통 배열의 크기, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀 함수인지 등이다
• 프로그램에 필요한 공간은 크게 고정 공간, 가변 공간 이 있는데, 시간적인 측면을 무시하고 공간 복잡도만 고려한다면 고정 공간보다는 가변 공간을 사용할 수 있는 자료 구조가 더 효율적이다
• 함수 호출 시 할당되는 지역 변수들이나 동적 할당되는 객체들도 모두 공간이 필요하다
• 특히 재귀 함수의 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요해서 재귀적(Recursive)으로 짤 수 있고, 반복문으로도 짤 수 있는 경우에는 반복문으로 짜는 것이 더 효율적이라고 본다

 

 

 

 

 

 

✨ 시간 복잡도 vs 공간 복잡도

• 시간 복잡도는 "얼마나 빠르게 실행되느냐", 공간 복잡도는 "얼마나 많은 자원이 필요한가" 이다
• 좋은 알고리즘은 빠른 시간 내에 적은 자원을 사용하는 것이다
• 그러나 시간과 공간은 반비례적인 경향이 있다
• 또한 현재는 컴퓨터의 성능이 좋아져 메모리가 넉넉하기 때문에, 알고리즘의 척도는 시간 복잡도를 위주로 판단한다

 

 

---

참고)

https://velog.io/@cha-suyeon/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

[Algorithm] 시간 복잡도, 공간 복잡도

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

[Algorithm] 알고리즘 시간복잡도에 대하여

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

[Algorithm] 알고리즘 공간복잡도에 대하여

https://madplay.github.io/post/time-complexity-space-complexity

시간복잡도와 공간복잡도(Time Complexity Space Complexity)