[알고리즘]1. 시간과 공간

작성한 알고리즘이 문제를 해결할 수는 있어도 만약 속도가 1년 이상이 걸린다면 해당 알고리즘은 좋은 것이라고 할 수 없다.

알고리즘이 적은 시간을 사용한다는 것은 더 빠르게 동작한다는 것이다.

웹에서 검색이 빠르게 이루어진다면 사용자의 답답함을 줄일 수 있다는 것이고, 게임 로딩 시간이 빨라진다면 금쪽같은 휴식 시간을 조금 더 효율적으로 즐길 수 있을 것이다.

시간 뿐만 아니라, 알고리즘은 공간과도 관련이 있는데 이는 메모리 사용량을 의미한다.

알고리즘이 빠르더라도 엄청 많은 메모리량을 사용한다면 작업을 수행할 수 없을 것이다.

띠라서 알고리즘을 작성할 때는 시간과 공간을 신경쓰는 것이 중요하다.

이를 보통 '시간복잡도', '공간복잡도'라고 한다.

 

알고리즘의 시간은 대부분 반복문이 지배한다.

자동차와 자전거를 예로 들어보자.

자전거는 자동차와 달리 시동을 켤 시간도 필요 없고 엔진 경고등을 확인할 시간도 필요없다.

출발하기까지의 시간은 자전가가 훨씬 더 빠르다.

하지만 서울에서 부산으로 이동한다고 가정해보자.

사이클에 미치지 않고서야 대부분 자동차가 더 빠르기 때문에 자동차를 이용할 것이다.

주행하는 시간이 모든 시간을 지배하기 때문에 발생하는 현상이다.

만약 거리가 더 증가한다면 시간의 격차가 더 벌어질 것이다.

프로그래밍에서도 입력의 크기가 커질수록 반복문이 알고리즘의 수행 시간을 지배한다.

 

시간복잡도는 주로 big-O 표기법을 이용한다.

변수에 대해서 해당 알고리즘의 수행 시간을 계산하는데, 만약에 반복문이 n번 반복한다면 해당 시간복잡도는 O(n)이다.

만약 변수가 여러개라면 가장 빨리 증가하는 항들(정확히는 아니지만 큰 값이라고 보면 되요)을 제외하고 모두 제거한다.

시간복잡도가 높다는 말은 입력의 크기가 증기할 때, 알고리즘의 수행 시간이 더 빠르게 증가한다는 것이다.

따라서 시간복잡도가 낮다고 해서 언제나 더 빠르게 수행하는 것은 아니다.

중요한 것은 입력의 크기이다.

입력의 크기가 충분히 작을 때는 시간복잡도가 높은 알고리즘이 더 빠르게 수행할수도 있다는 것이다. (입력의 크기가 매우 작을 경우에는 시간복잡도는 큰 의미가 없을 수도 있다.)

따라서, 문제의 입력의 크기에 따라 적재적소에 맞는 시간복잡도를 가진 알고리즘을 설계하는 것이 중요하다.

또한 시간복잡도는 최고와 최악, 그리고 평균적인 경우마다 모두 다르기 때문에 세 가지 상황을 고려해야한다.