자료구조와 알고리즘 ft. 수업/알고리즘 성능 분석

2. 점근 표기법

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

1. 알고리즘 성능 측정 기준과 수행 시간

알고리즘 성능 측정 기준 정확성 : 정확하게 동작하는가? => 알고리즘이 입력값에 대해 정해진 절차를 수행하여 결과적으로 정확한 출력을 제공하는가를 가리키는 기준 작업량 : 얼마나 적은 연산을 수행하는가? => 요구되는 기능을 수행하기 위해 알고리즘이 수행해야 하는 작업의 양이 얼마나 되는가를 가리키는 기준 ex) 버블 정렬에서 정렬을 수행하기 위해 비교 연산을 몇 번 수행하는가? 라는 질문에서 '비교횟수' 메모리 사용량 : 얼마나 적은 메모리를 사용하는가? => 말 그대로 해당 알고리즘이 작업을 수행할 때 사용해야 하는 메모리의 양 단순성 : 얼마나 단순한가? => 알고리즘을 짤 때는 보기쉽고 단순해야 한다 최적성 : 더 이상 개선할 여지가 없을 만큼 최적화가 되어있는가? => 최적화를 거친 알고리즘들..