'Big Ω' 태그의 글 목록

Big O Big O는 실행시간의 상한(최악)을 나타낸다. 아래 차트는 알고리즘을 실행하는데 걸리는 시간을 표현한 것이다. 이 차트를 공식으로 표기한 것이 Big O 표기법이다. Big O의 O는 on the order of의 약자로, 쉽게 생각하면 '~만큼의 정도로 커진다'라는 뜻이다. 따라서 O(n)은 n만큼 커진다는 것을 의미하고 n이 늘어날수록 선형적으로 증가하게 된다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 그냥 O(n)과 같다. 아래의 표기가 실행시간을 나타내기 위해 많이 사용된다. O(n^2) O(n log n) O(n) - 선형 검색 O(log n) - 이진 검색 O(1) Big Ω(오메가) Big Ω는 실행시간의 하한(최선)을 나타낸다. 아래의 표기가 실행시간..