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

자료구조란 ? 효율적으로 데이터를 저장하고 관리할 수 있는 데이터 집합

 

1. 복잡도

먼저 복잡도란 '알고리즘의 성능과 효율성을 나타내는 척도'입니다. 크게 시간 복잡도와 공간 복잡도로 나눌 수 있다.

 

알고리즘을 성능을 평가할 때 주로 수행 시간과 메모리 사용량을 기준으로 두는데, 이 중 수행 시간에 해당하는 것이 시간 복잡도이고 메모리 사용량에 해당하는 것이 공간 복잡도이다.

 

1-1. 시간 복잡도

시간 복잡도란 프로그램에서 특정 크기의 입력을 기준으로 할 때 수행되는 연산의 횟수를 나타낸다.

• 최선의 경우 (Best Case)
  최적의 입력을 한 상태에서, 작업을 완료하는 데 필요한 연산 횟수
• 최악의 경우 (Worst Case)
  최악의 입력을 한 상태에서, 작업을 완료하는 데 필요한 연산 횟수
• 평균의 경우 (Average Case)
  여러 경우의 수를 고려하여, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

➡️ 알고리즘 분석 시 평균의 경우와 최악의 경우가 가장 많이 활용되며, 알고리즘이 복잡해질수록 평균을 구하기 어려워져 최악의 경우로 알고리즘 성능을 파악한다.

 

1-2. 공간 복잡도

공간 복잡도란 프로그램을 실행했을 때 필요로 하는 공간(메모리)의 양를 나타낸다. 즉, 시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)을 사용하는지를 판단한다.

 

시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단한다.

 

2. 빅오 표기법 (Big-O notation)

 

빅오 표기법(Big-O notation)은 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법이다.

 

빅오 표기법이 가장 많이 사용되는 이유는 알고리즘 효율성을 최악의 경우, 즉 상한선 기준으로 표기하기 때문이다.

 

👉🏻 빅오 표기법은 '상수항을 무시'하고, '가장 영향력이 큰 항만 고려'한다는 특징이 있다 !