45

시간복잡도, 공간복잡도

시간복잡도란?

1. 우리가 작성한 코드는 실행시간이 얼마나 걸릴까?
   실행해보기 전에 정확한 시간을 추측하는 것은 힘들겠지만
   반복문을 몇 번 사용했는지, 입력값은 어떻게 되는지 등을 통해 대략적으로 이 정도 되겠구나를 추측할 수 있다. 즉, 우리는 입력값과 연산 수행 시간의 상관관계를 나타내는 척도를 시간 복잡도라고 한다.

2. 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 같는 소스라면 시간이 적게 걸리는 것이 좋은 소스입니다.

빅-오 표기법

시간 복잡도에는 빅-오 표기법이라는 개념이 나옵니다.
예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷면이 나오지만 운이 안 좋다면 n번 만큼 동전을 튕겨야 하는 경우가 발생합니다.
이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부릅니다.

공간복잡도?

공간 복잡도(Space Complexity)란, 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말합니다.