# 좋은 알고리즘이란? ## 목차 --- 1. 무엇? 2. 분석 기준 3. 분석 연습 ## 1. 무엇? --- 처리 시간이 짧고, 사용 메모리가 적을수록 좋음. 이 두 가지 측면을 각각 시간 복잡도(time-complexity) 및 공간 복잡도(space-complexity)라 함. ## 2. 분석 기준 --- 같은 일을 더 빨리 끝낼수록 좋음. 이를 평가하는 기준이, 성장률(growth-rate)임. ### 성장률 성장률이란, 입력 데이터의 크기에 따른 처리 시간 비율을 말함. 핵심이 되는 7가지 지표가 있음.  ### 빅오 표기법 빅오 표기법(O(1), O(n), ...)은 알고리즘 분석의 기초가 됨. 이는 최악의 경우에 걸릴 시간을 나타냄. 예를 들어 O(1), O(n), O(n^2)은 아래와 같음. - O(1): 데이터 크기에 상관없이, 고정 시간 소요. - O(n): 데이터 n개 입력 시, n에 비례하는 시간 소요. - O(n^2): 데이터 n개 입력 시, 그 크기의 제곱에 비례 시간 소요. ## 3. 분석 연습 --- ### 배열 중 가장 큰값 찾기 예 해당 코드의 수행 속도 즉, 성장률은 얼마일까? 주석을 참고. ``` double arrayMax(double[] data) { int n = data.length; // O(1) double currentMax = data[0]; // O(1) for (int i = 1; i < n; i++) { // O(n) if (data[i] > currentMax) // O(1) currentMax = data[i]; // O(1) } return currentmax; // O(1) } ``` 정답은 O(n). 왜? 실제 모든 수행 시간을 더하면 O(n) + 3O(1). 그러나 가장 높은 차수만이 의미가 있음. 따라서 나머지 제거. ### 낮은 차수 제거 이유 n의 크기가 충분히 클 수록, 낮은 차수의 값은 의미가 무색해 짐. $$ n^6 + 1000n^2 + 7 $$ - n = 1일 때, 수행시간 => 1 + 1000 + 7 - n = 10일 때, 수행시간 => 1000000 + 100000 + 7 - n = 100일 때, 수행시간 => 1000000000000 + 10000000 + 7 - ... ## 요약 --- - 좋은 알고리즘 => 빠르고, 효율적인 것. - 분석 기준 => 성장률. - 빅오 표기법 => 최악의 경우 걸리는 복잡도.