Today I Learned - Time complexity

 

 

시간 복잡도(Time complexity)란?

 

알고리즘을 구성하는 명령어들이 몇번이나 실행됬는지 센 결과와

각 명령어의 실행시간(execution time) 을 곱한 합계를 의미한다.
 

그러나 각 명령어의 실행시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에

알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만을 고려하게 된다.

 

 

 

 

O(1): 입력자료의 수에 관계 없이 일정한 실행 시간을 갖는다.

 

O(log n): 만약 입력 자료의 수에 따라 실행 시간이 이 log N 의 관계를 만족한다면

N이 증가함에 따라 실행시간이 조금씩 늘어난다. 이 유형은 주로 커다란 문제를

일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형이다.

 

O(n): 입력 자료의 수에 따라 선형적으로 실행 시간이 걸리는 경우이다.

이는 입력 자료 각각에 일정 정도의 동일한 처리를 할때 나타나는 경우이다.

 

O(n²)(quadratic): 이 유형은 이중루프내에서 입력 자료를 처리 하는 경우에 나타난다.

n값이 큰값이 되면 실행 시간은 감당하지 못할 정도로 커지게 된다.