시간복잡도와 공간복잡도

파이썬 스터디 중에 여러 질문이 들어왔다...

선형대수도 모르고 여러모로 모르는게 많은 초심자라 정신이 없었다ㅜㅜ

 

그래서 멘토님이 주신 과제!!

-시간복잡도와 공간복잡도 공부하기-

---

우선 시간복잡도와 공간복잡도는 알고리즘의 성능을 판단하는데 쓰인다.

그래서 좋은 알고리즘인지를 확인한다.

시간복잡도와 공간복잡도 모두 작은 것이 효율적이고 좋은 알고리즘을 의미한다.

 

1. 시간복잡도(Time Complexity)

: 알고리즘을 수행하는데 걸리는 시간을 분석한 결과를 말한다.

 

- 시간복잡도는 '실행시간'이 아닌 '연삿횟수'를 센다.

- 만약 '실행시간'으로 시간복잡도 계산하면 

 1) 모든 컴퓨터(ex. 일반 컴퓨터, 슈퍼 컴퓨터)에서 동일한 결과를 산출하지 못한다.

 2) 측정을 위한 완성된 프로그램이 필요하다.

 

-'연산횟수'로 계산했을 때의 이점은

 1) 실행이 필요하지 않다.

 2) h/w, s/w가 필요하지 않다.( 수도코드로 충분히 계산이 가능하다)

 3) 모든 컴퓨터에서 동일한 결과를 산출한다.

 

 

시간복잡도를 표기하는 3가지 방법 

① 빅오(Big-O)표기법 : 최악의 실행 시간
② 오메가(Big-Ω)표기법 : 최상의 실행 시간
③ 세타(Big-θ)표기법 : 평균 실행 시간

보통 빅오 표기법을 사용하는 이유는 Worst 실행시간이어도 그 시간은 보장해줄 수 있기 때문이다.

 

 

2. 공간복잡도(Space Complexity)

: 알고리즘을 수행하는데 메모리 사용량(RAM의 양)을 분석한 결과를 말한다.

 

- 고정 공간과 가변 공간을 합친 포괄적인 개념

- 고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말한다.

- 가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 즉 동적으로 필요한 공간을 말한다.

 

---

 

좋은 알고리즘이란?  

“시간도 적게 걸리고 자원의 사용도 적은 것” 

 

But, 시간과 공간은 반비례적인 경향

그래서 알고리즘의 척도는 시간 복잡도를 위주로 판단한다.
즉, 시간 복잡도만 괜찮다면 공간 복잡도는 어느 정도 이해해준다.

 

 

 

 

---

Reference

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