Today
-
Yesterday
-
Total
-
  • BigOhNotation
    잡소리 2004. 11. 10. 16:22
    ComputationalComplexity를 표기하는 방법중 하나로써 Algorithm의 성능을 정형적으로 표현하는 일반적인 표기법. SeeAlso EstimateOrderOfAlgorithm

    보통 알고리즘의 성능은 수행하는 자료의 크기(n)의 함수로 표현된다.

    간단한 규칙들

    O(c) = O(1) : 상수항. 자료의 양에 관계없이 일정한 시간이 걸릴경우.
    O(cT) = cO(T) = O(T) : 계수들은 생략한다.
    O(T1) + O(T2) = O(T1 + T2) = max(O(T1), O(T2)) : 더할때는 큰것을 선택.
    O(T1)O(T2) = O(T1 T2) : 곱은 간결히
    따라서, 다음처럼 표현한다.



    일반적인 문제별 BigOhNotation

    BigOhNotation
    example

    O(1)
    자료의 집합에서 첫번째 항목가져오기

    O(lg n)
    자료의 집합을 반으로 나누고 그 반을 다시 반으로 나누는 과정의 반복

    O(n)
    자료집합을 순회하기

    O(n lg n)
    자료집합을 반복해서 둘로 나누고 나뉘어진 반을 순회하는것

    O(n^2)
    한 집합의 각자료에 대해 같은 크기의 다른 집흡을 순회하는것

    O(2^n)
    집합의 모든 부분집합을 생성하는것

    O(n!)
    집합의 모든 순열을 생성하는것

    '잡소리' 카테고리의 다른 글

    서울시 공무원 식수 '아리수'  (0) 2004.11.10
    [펀글] 보성 차밭  (0) 2004.11.10
    [펀글] 우낭  (0) 2004.11.10
    벚꽃 (사쿠라)  (0) 2004.11.10
    [펀글] ASF/ASX/WMV/MOV/AVI에서 VCD로 굽기  (0) 2004.11.10

    댓글

Designed by Tistory.