시간복잡도(Time Complexity)의 개념

알고리즘을 처리하는데 걸리는 시간

​

연산을 실행 시간으로 측정하기 어려운 이유

검색이라는 연산을 할 때 최초의 CPU 4004를 탑재한 컴퓨터와 최신 CPU를 탑재한 컴퓨터는 속도에서 큰 차이를 보일 것이다. 같은 CPU라도 작업 프로세서를 많이 띄워놓고 있다면 프로그램 실행이 느려질 수 있다. 이렇게 프로그램 연산 속도를 시간으로 따지는 경우 하드웨어에 따라, 작업 상황에 따라 항상 달라질 수 밖에 없다. 또한, 시간은 정확히 1.00초, 2.00초와 같이 딱 떨어지지도 않을 것이다. 시간으로 측정할 경우, 프로그램 알고리즘뿐만 아니라 다른 요소까지도 고려해야 하는 문제가 생긴다.

​
​
​

실행 횟수(단계 측정)

그래서 연산의 속도를 측정할 때는 ‘시간’이 아니라 ‘단계’ 별로 따진다. 연산 A에서 5단계가 필요하고, 연산 B에서 100단계가 필요하다면, 하드웨어 성능에 상관없이 연산 A가 B보다 빠를 것이라고 가정할 수 있다. 그래서 프로그램을 짤 때는 실행에 필요한 각 단계를 계산해, 이 단계를 가장 최소화하는 방법을 찾는다.

​
​