시간복잡도와 공간복잡도

시간복잡도

: 알고리즘에 사용되는 총 연산 횟수. ( 실행 시간 아님!!! )

*연산 : + , -, / , *, =, ==, <, > ...

함수 return 문에서 연산횟수 1이라고 생각. 

코드의 효율과 알고리즘을 판단하는데 사용된다.

Big-O 시간 복잡도

: 시간복잡도 함수의 가장 높은 차수. 

계수 X. 시간복잡에 미치는 영향이 매우 미미하기 때문이다.

 

aN + b = O(N)

aNlogN + b = O(NlogN)

aN^2 + bN + c = O(N^2)

-> N의 크기가 커질수록 점점 복잡도의 차이가 커진다.

 

계산법칙 1 : For/While loop이 한 번 중첩될 때마다 O(N)

계산법칙 2 : 자료구조(ex. 배열) 사용, 다른 함수 호출에는 각각의 O(N) 파악.

* set은 O(1). 배열.sort()는 O(NlogN)

계산법칙 3 : 매번 절반씩 입력값이 줄어들면 O(logN)

* ex) 8 -> 4 -> 2 -> 1  : log(8) = 3

 

 

공간복잡도

: 알고리즘에 사용되는 메모리 공간의 총량

* 시간복잡도보다 덜 중요함.