자료구조 05 : 시간 복잡도 (time complexity)

수학과 같이 한 문제를 해결하는 데에

여러가지 알고리즘이 있을 수 있다.

 

 

알고리즘 복잡도 표현 방법 : 시간 복잡도★

이때 알고리즘 실행 속도를, 얼마나 빠르게

문제를 해결하는 알고리즘인지 측정하는

것이 시간 복잡도 이다.

코딩 문제를 풀다가 나오는 O(n), O(n²)이 한 예이다.

당연히 O(n)이 O(n²)보다 좋은(빠른) 코드이고,

이 시간은 반복문에서 크게 좌지우지된다.

 

 

알고리즘 복잡도 표현 방법 : 공간 복잡도

알고리즘이 사용하는 메모리 사이즈를

측정하는 기준이다. 사람이 간단히 계산할 수

있는 부분이 아니기 때문에 시간 복잡도에

비해 중요도가 살짝 떨어지는 편이다.

 

※ k,k'는 상수

무조건 k회 실행하면 O(1),

n에 따라 n번, kn+k' 실행하면 O(n)

n에 따라 n²번, kn²+k'번 실행하면 O(n²)

이라고 표현한다.

만일 2n²+3n과 같이 다항식 형태로

나온다면 n을 무한으로 lim 때리면 된다.