시간복잡도 개념

1 시간 복잡도 나타나는 수

1(constant) : 입력자료의 수에 관계없이 일정한 실행시간 갖음

Log N : 입력자료의수에 따라 시간이 점점 시간이 조금씩 증가함 - 주로 큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형. 예) 효율이 좋은 검색 알고리즘.. 이 뭐가 있드라. 이진탐색 같은 것 - Log­2n

N(Linear) : 입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우- 입력자료 각각에 일정량(시간)이 할당되는 경우

N Log N :  이것은 주로 큰문제를 일정한 크기를 갖는 문제로 쪼개고(Log N), 다시 그것들을 하나로 모으는 경우에 나타남 (N). 예) 효율 좋은 정렬 알고리즘. quick sorting, heap sorting 등. link: http://wrice.egloos.com/3097929

N² :  이중루프내에서 입력자료를 처리할때 발생함.

N³ :  얘는 삼중 루프내에서 입력 자료 처리할때 발생. 

※ 알고리즘에서 가장 기본이 되는 것은 정렬과 검색임 !!!

 

2 시간 복잡도란?

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

(+ execution time 인데, h/w 의존하기 때문에 일단 이것은 제외함) 

주로 시간과 공간의 반비례하는데, 요즘에는 시간이 우선 !!! ( because of h/w tech was improved)

 

3 시간 복잡도 표현(Notation)

Big O - O(N) : 실행 시간 상한 표현 (가장 많이 쓰임) - 최악의 시간 계산 

Ω      - Ω(N) : 실행 시간 하한 표현                        

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

 

출처: <http://cafielo.tistory.com>