시간복잡도, 공간복잡도?

복잡도(Complexity)란?

• 알고리즘의 성능과 효율성을 나타내는 척도이다.
• 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)로 나눌 수 있다.

---

시간복잡도(Time Complexity)
시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 수량적으로 나타낸다.

일반적으로 입력 크기 ( n )에 대한 함수로 표현하고, 보통 최악의 경우를 기준으로 분석한다.

 

시간 복잡도는 다음과 같은 표기법으로 나타낼 수 있다.

• O(1): 상수 시간 복잡도 (입력 크기에 관계없이 일정한 시간)
• O(log n): 로그 시간 복잡도 (입력이 커질수록 시간 증가가 느리게 증가)
• O(n): 선형 시간 복잡도 (입력 크기에 비례하여 시간 증가)
• O(n log n): 선형 로그 시간 복잡도 (정렬 알고리즘에서 자주 발생)
• O(n²): 이차 시간 복잡도 (입력 크기가 두 배가 되면 시간은 네 배 증가)

---

공간복잡도(Space Complexity)
공간 복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리 공간의 양을 수량적으로 나타낸다.

마찬가지로 입력 크기 ( n )에 대한 함수로 표현된다.

 

공간 복잡도는 다음과 같은 요소를 포함한다.

• 고정 공간: 알고리즘 실행에 필요한 상수적인 메모리
• 가변 공간: 입력에 따라 달라지는 메모리 (예: 배열, 리스트 등)

 

공간 복잡도 또한 다음과 같은 표기법으로 표현될 수 있다.

• O(1): 상수 공간 복잡도 (입력 크기에 관계없이 일정한 메모리)
• O(n): 선형 공간 복잡도 (입력 크기에 비례하여 메모리 증가)

---

시간 복잡도와 공간 복잡도는 알고리즘 선택 시 중요한 고려 요소다.

 

 

질문, 틀린 정보, 알고 싶은 정보는 댓글로 알려주시면 공부해서 올리도록 하겠습니다.