[윤성우의 열혈 자료구조] 시간 복잡도 & 공간 복잡도

시간 복잡도 : 얼마나 빠른가

공간 복잡도 : 얼마나 메모리를 적게 쓰는가

시간 복잡도가 더 중요하다.

 

왜냐하면 메모리를 많이 쓰느냐 적게 쓰느냐가 중요한게 아니다.

알고리즘의 시작과 끝이 있다

메모리는 누적해서 쓰진 않는다.

다시말해 메모리를 지웠다 썼다 할 수 있는 것이다.

이에 따라 메모리의 접근시간도 공간복잡도에 따져보자 할 수 있지만 메모리의 접근시간은 시간 복잡도의 cpu가 알고리즘을 처리하는 시간에 비하면 큰 문제는 아니라는 것이다. 몰론 공간복잡도가 필요없다는것은 아니지만 시간 복잡도에 비하면 덜 중요하다.

 

⁕ 시간 복잡도의 평가방법

연산의 횟수를 세어서 평가한다.

데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다.

예)

y:시간

x:데이터

T(n) -> y=2x

함수를 보고 알 수 있는 것 : 데이터가 커질 수록 연산시간이 커진다.

이러한 알고리즘의 성능을 가늠하기 위해 함수가 필요하다.

 

⁕ 알고리즘의 수행속도 비교기준

데이터수가 적은 경우 수행속도는 큰 의미가 없다.

데이터의 수에 따른 수행 속도의 변화정도를 기준으로 한다.

->데이터가 적을때 알고리즘 B가 유리하다고해서 알고리즘B를 사용할 필요가 없다는 것이다.

왜냐하면 데이터가 적다면 그만큼 연산횟수도 적고 연산시간도 얼마 안 걸리기때문에 의미가 없다.

 

 

윤성우의 열혈 자료구조 : 네이버 도서