공부/알고리즘2011. 6. 24. 21:13


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

함수의 비교
 

Θ,Ω,ο,ω 를 관계로 보면
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


Posted by skyjumps