ezwy

알고리즘의 시간 복잡도(타임 컴플렉시티)

프로그램의 실행시간은 하드웨어에 따라 상이하므로 객관적 기준이 될 수 없다.

알고리즘의 수행 시간을 지배하는 것은 반복문이다. 시간복잡도는 반복문이 수행되는 횟수로 측정한다. 예를 들어 n번 수행되는 for문 안에 다시 n번 수행되는 for문이 있다면 n제곱의 시간 복잡도를 가진다. 반복문 내에 명령문이 여러 개 있을 수도 있는데 더 이상 분해될 수 없는 연산의 수를 세면 된다. (이하 원자 연산) for 내에 원자 연산이 3개 있고 10번 반복된다면 복잡도는 30이다.

for(i=1 ; i<n ; i++) {

a = b+i ;

}

위와 같은 알고리즘이 있다면 소괄호안의  i=1은 한번만 사용되기 때문에 1, 그리고 소괄호 안의 비교연산과 증가가 각각 1회로 2개, 대괄호 안의  a= b+i는 분해가 될 수 있으므로 덧셈과 대입 연산은 모두 하나의 독립적인 연산이다. b와 i를 더하는 연산이 1개, 그리고 대입하는 연산이 1개이며 i=1을 제외한 부분들은 n번 반복되므로 시간복잡도는 4n + 1 이 된다.

또한 하나의 반복문이 n번 반복되고 다른 반복문은 100번 반복된다면 복잡도는 n+100이다. 하지만 n이 커질 수록 100의 영향은 거의 무의미해 진다. 따라서 n이 무한대로 갈 때의 복잡도만을 계산하는데 컴퓨터 연산에서 n은 사람이 상상하기 힘들정도로 큰 경우에만 의미가 있고 n이 작을 때는 걸리는 시간이 적어 또 다른 의미로 복잡도가  의미가 없으므로 n이 무한대인 경우의 복잡도만을 다룬다.