[자료구조]01. 알고리즘의 성능분석 방법 - 시간복잡도 / 공간복잡도

  

시간복잡도와 공간 복잡도

우리는 잘 동작하고 좋은 성능까지 보장받기를 원하기 때문에 알고리즘을 분석 및 평가 할 수 있어야 한다.

"알고리즘이 얼마나 빠르고 또는 느린가 "  " 어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰거나 많이쓰나"

  -> 알고리즘의  수행시간  "속도"                   -> 알고리즘이 필요로 하는 기억공간의 양     "메모리의 사용량"

  -> "시간 복잡도"                                       -> " 공간 복잡도"

---

시간 복잡도 함수

시간복잡도는 알고리즘의 수행시간 분석을 뜻한다.

연산의 횟수를 통해 알고리즘의 빠르기를 판단한다. = 연산 횟수 통해 시간복잡도를 표시

연산의 수행횟수는 객관적인 근거이다.

데이터의 수를 x로, 연산횟수의 함수를 y로 설정하여 함수 T(n) 으로 구성한다. 

왜 함수식으로 구성할까?

그 이유는 함수로 만들어놓으면 그래프로 만들어 둘 수 있다.

이렇게 그래프를 그려놓으면 데이터의 수가 늘어남이 한눈에 들어온다.

즉 '데이터 수'에 따른 '연산횟수'의 변화정도를 알 수 있다.

알고리즘의 수행속도 비교 기준에 대해서 

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

사진을 보면 데이터의 수가 적은 경우에는 알고리즘 b가 우수하다고 볼 수 있다. 이후 데이터 수가 증가한 이후에는 알고리즘 a가 우수하다고 볼 수 있으므로 데이터가 적을 때에는 b를 사용하고 많을 때에는 a를 사용하면 되는거아니야?

답은 아니다. 왜냐하면 여기서 데이터의 수가 적은 경우에는 연산의 횟수 수행속도는 큰 의미가 없다.

데이터의 수가 증가함에 따라 연산의 횟수가 중요하다.

데이터 수에 따른 수행 속도의 변화 정도를 기준으로 하기 떄문에

" '데이터 수'가 '늘어날 때' 어떠한 유형을 보이며 증가하는 가 ?" 즉 증가하는 패턴이 중요하다.