점근 표기법

2. 점근 표기법

점근(차츰 점, 가깔울 근) 표기법 => 알고리즘의 수행시간을 대략적으로 나타내는 방법 ex) 데이터를 정렬하는데 필요한 작업 횟수 : (n^2 + 5n ) vs ( 27n ) => 데이터의 크기가 커지면 커질수록 최고차 항을 제외한 나머지 항의 영향은 거의 없다 => 때문에 점금 표기법에서는 알고리즘의 성능을 최고차 항으로만 '대략적으로' 표시한다 대표적인 점근 표기법 3가지 O(Big O) 표기법 Ω (Big Omega) 표기법 Θ (Big Theta) 표기법 O(Big O) 표기법 최악의 경우 알고리즘 수행 시간 즉, 아무리 열악한 조건이라도 (입력이 아무리 크더라도) O 표기법으로 표현된 성능 수준에서 알고리즘이 종료된다는 의미 가장 많이 사용하는 알고리즘 성능 표기법 사용방법 대문자 O를 쓰고 ..