시간 복잡도 (time complexity) 이란?

시간 복잡도 (time complexity) 이란?

 

양질의 프로그램을 구분하는 척도 중 한갈래인 시간복잡도는 작성한 코드들인 상황을 해결하는데에 있어서 어느정도의 시간을 많이 필요로 하는지 알아보는 것이다.

 

문제를 해결하기만 하면 이것이 구동되는데 걸리는 시간같은것은 중요하지 않지 않느냐라고 생각해보는것도 타당하지만 수행 시간이 늦어질수록 해당 프로그램이 씨피유를 점유하는 기간이 늘어나고 그러면 결국 CPU가 다른 프로세스를 처리하지 못하게되어 프로그램의 능률이 낮아질수 있다.

 

이런 이유로 프로그램을 작성함에 있어서 시간복잡도를 생각해서 코드를 짜야 한다. 시간복잡도에는 갖가지 항목들이 있는데 그 중에서도 최대 걸리는 시간의 개념이 가장 필요한 개념이라고 볼 수 있다. 이걸 빅오 표기라고 일컫는다. 프로세싱에 요구되는 타임의 맥스값을 나타내는 것이다.

 

같은 문제를 푸는데 있어서, 똑같은 리절트를 불러온다고 하더라도 탐색법을 어떻게 짜느냐에 따라서 소요시간이 천차만별이다. 탐색을 하는 이용법에는 순차적인 탐색법, 이진트리 탐색법과 같은 여러가지 방법들이 존재하는데 어떤 환경에서 그리고 조건에 데이터가 들어가 있는지에 따라서 결국 요구되는 시간이 달라진다는 것이다. 이런 이유로 조금더 빠른 알고리즘을 짜내기 위해 시간복잡도를 생각해서 코드를 짜는 것이다.