시간복잡도

시간복잡도란: 시간 복잡도는 알고리즘을 구성하는 명령어들이 몇 번이나 실행이 되는지를 센 결과에 각 명령어의 실행시간을 곱한 합계를 의미한다.

 

시간복잡도 표기법: Big-O 표기법이 있는데, 이는 실행 시간 n을 O(n)으로 표기한다.

 

1. O(1) : 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다. (Constant Time)

 

- 입력되는 데이터양과 상관없이 일정한 실행 시간을 가진다.

- 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.

 

2. O(n) : 입력 데이터의 크기에 비례해서 처리시간에 걸리는 알고리즘을 표현할 때 사용 (Linear Time)

 

- 데이터양에 따라 시간이 정비례한다.

- Linear search, for 문을 통한 탐색을 생각하면 된다.

 

3. O(n^2) : Quadratic Time

 

- 데이터양에 따라 걸리는 시간은 제곱에 비례한다. (효율이 좋지 않음, 사용 X)

- 해당 유형은 이중 Loop내에서 입력 자료를 처리 하는 경우에 나타난다. N값이 큰 값이 되면 실행 시간은 감당하지 못할 정도로 커지게 될 것이다.

- 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱

 

4. O(log n) : Binary search tree access(이진 검색) - search(검색), insertion(삽입), deletion(삭제)

 

- 데이터양이 많아져도, 시간이 조금씩 늘어난다.

- 시간에 비례하여, 탐색 가능한 데이터양이 2의 n승이 된다.

- 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

- 만약 입력 자료의 수에 따라 실행 시간이 이 log N의 관계를 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다. 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형이다.