계산 복잡도(시간, 공간)

계산 복잡도

계산복잡도(complexity) : 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한지 나타낸 정도

 

O 표기법 : 계산 복잡도를 표현하는 방법 ('빅 오 표기법'이라고도 함)

 

• O(n) : 필요한 계산 횟수가 입력 크기에 '정비례'할 때는 O(n)이라고 표현한다.(계산 횟수가 입력 크기만큼 계속해서 늘어남)
• O(1) : 입력 크기 n과 필요한 계산의 횟수가 무관하다면, 즉 입력 크기가 커져도 계산 시간이 더 늘어나지 않는다면 모두 O(1)로 표기한다. (입력크기 n이 무엇이 오든 항상 계산 횟수가 늘어나거나 하지 않음)

어떤 문제를 푸는 알고리즘이 두가지 O(n)과 O(1)이 있다면 평균 입력 크기나 각 알고리즘의 실제 계산 방식 등에 따라 차이는 있을 수 있지만, 입력 크기가 큰 문제를 풀 때는 보통 O(1)인 알고리즘이 훨씬 더 빠르다.

 

정보(계산복잡도 : 시간 복잡도와 공간 복잡도)

알고리즘의 계산 복잡도는 시간 복잡도(time complexity)와 공간 복잡도(space complexity)가 있다.

 

• 시간 복잡도는 어떤 알고리즘을 수행하는 데 얼마나 오랜 시간이 걸리는지 분석한 것이다. 
• 공간 복잡도는 어떤 알고리즘을 수행하는 데 얼마나 많은 공간(메모리/기억 장소)이 필요한지 분석한 것이다.