시간 복잡도 관련 공부

시간 복잡도란? - 알고리즘을 구성한 명령어가 실행된 횟수 (frequency of calling command)

알고리즘을 분석하거나 비교할때 시간 중심적으로 분석하느냐에 관한 내용

(공간 복잡도 : 메모리 공간을 차지하는 관점으로 알고리즘을 해석, 분석하는 개념)

 

 

1. 시간 복잡도를 나타내는 형태

 

- 상수형 1(constant) : 입력자료의 수와 상관없이 일정한 실행시간

 

- 로그형 log n : 입력자료의 수에 따라 시간이 조금씩 증가, 하나의 큰 크기의 과제를 작은 과제로 쪼개나가는 유형

    예)  이진 검색 알고리즘

 

- 선형 n : 입력 자료의 수에 따라 선형적으로 실행 시간이 증가, 입력자료 각각에 일정시간이 할당되는 유형

 

- 선형 로그형 n log n : 큰 크기의 과제를 일정한 크기의 과제로 쪼개(log n), 다시 모으는 유형(n)

  예) 정렬 알고리즘(quick, heap)

 

- 평방형 n^2 : 이중 루프내에서 입력자료 처리하는 유형, n^3은 삼중 루프.....

 

 

 

 

 

2. 시간 복잡도 표현

 

Big O - O(N) : 가장 오래 걸리는 실행 시간 표현 (가장 많이 쓰이는 방식)

Ω      - Ω(N) : 가장 짧은 실행시간 표현

Θ      - Θ(N) : 평균 실행 시간 표현

참고: http://cafielo.tistory.com/entry/시간복잡도-개념-및-구하기 [cafielo]