컴퓨터과학 🖥️/자료구조&알고리즘
[알고리즘] 점근성능
#1 점근성능 입력크기(실제 처리하는 데이터 개수) n이 무한대로 커짐에 따라 결정되는 성능!데이터 개수가 증가하면 알고리즘 성능결정에 가장 큰 요인은 무엇인지 따지는 것! f(n) = 10n + 9 f(n) = n^2 / 2 + 3n n=5 59 27.5 n=10 109 80 n=15 159 157.5 n=16 169 176 n=20 209 260 ... ... ... 수행시간의 다항식 함수에서,데이터 개수가 증가할 수록(입력크기가 증가할 수록) 최고차항이 성능결정요인에 가장 큰 요인이 됨 계수없이 최고차항만으로 시간복잡도를 표현! 수행시간의 어림값이나 수행시간의 증가추세 파악이 용이하다 => 알고리즘의 우열을 표현! #2 점근성능 표기법 [정의1] 'Big-oh' 점근적 상한 ( O => 최악의 수행..
