O-notation
Upper bound. 이보다 커질 수 없다.
Ω-notation
lower bound. 이보다 작아질 수 없다.
Θ-notation
tight bound. upper bound도 될 수 있고 lower bound도 될 수 있다.
ο-notation (small O notation)
tight 하지 않은 upper bound
ω-notation (small Ω notation)
tight 하지 않은 lower bound
함수의 비교
Upper bound. 이보다 커질 수 없다.
Ω-notation
lower bound. 이보다 작아질 수 없다.
Θ-notation
tight bound. upper bound도 될 수 있고 lower bound도 될 수 있다.
ο-notation (small O notation)
tight 하지 않은 upper bound
ω-notation (small Ω notation)
tight 하지 않은 lower bound
함수의 비교
Θ,Ω,ο,ω 를 관계로 보면
Transitivity
aRb and bRc -> aRc
Reflexivity
aRa
Symmetry
aRb -> bRa
Transpose symmetry
aRb -> bR'a
Transitivity
aRb and bRc -> aRc
Reflexivity
aRa
Symmetry
aRb -> bRa
Transpose symmetry
aRb -> bR'a
'공부 > 알고리즘' 카테고리의 다른 글
8장 Sorting in Linear Time (0) | 2011.07.03 |
---|---|
7장 Quicksort (0) | 2011.07.03 |
Heapsort (1) | 2011.06.30 |
4 Recursion (0) | 2011.06.28 |
2장 insertion sort, merge sort, binary search, selection sort, bubble sort (1) | 2011.06.23 |