본문 바로가기

(임시휴재) Fanta's Post

시간복잡도

시간복잡도
    처리해야하는 데이터의 양(N이나 n으로 표기)에 따라 걸리는 시간 절대적인 시간이 아닌 비례적인 시간을 나타냄.
    O(f(n))과 같이 표기.
    그렇게 믿을만한 건 못됨.

평균적인 경우
    일반적 입력데이터에 따라 걸리는 시간
    예) 반쯤정렬된 배열에 대한 정렬

최악의 경우
    가능한 최악의(오래걸리는) 입력데이터에 따라 걸리는 시간
    시간복잡도는 보통 최악의 경우로 나타냅니다.
    예) 반대로 정렬된 배열에 대한 정렬

시간복잡도의 예
    O(1)
        데이터의 크기에 상관없이 일정 시간 안에 실행을 마침
        상수시간이라고도 부름
    
    O(n)
        데이터의 크기에 비례하는 시간이 걸림
        선형시간이라고도 부름
        순차검색이 해당됨

    O(n2)
        n2에 비례하는 시간이 걸림
        선택정렬이 해당됨

    O(log n)
        이진검색이 해당됨

    O(n log n)
        힙정렬이 해당됨


[각 시간복작도에 대한 그래프]


각 시간복잡도에 대한 예제는........
알아오시는 게 숙제입니다.
미안해요.


ps. 하악 입학하기 전부터 야자를 뛰려니 막막하네요 ㅇㅅㅇ;;;;;;;;;;
     포스팅 날짜를 주말로 바꿔야겠습니다.

'(임시휴재) Fanta's Post' 카테고리의 다른 글

Bit twiddling Hack : 정수의 부호 계산  (0) 2009.02.28
변수의 범위  (3) 2009.02.21
포스팅연기  (1) 2009.02.11
순열과 조합  (2) 2009.02.05
퀵소트 알고리즘 구현  (0) 2009.01.22