알고리듬 분석

알고리듬을 평가하는 두가지 기준

1. 시간 : 알고리듬의 수행 속도의 특성을 분석
2. 공간 : 알고리듬의 메모리 사용 특성을 분석

 -> 시간이 빠르면서 메모리도 더 적게 사용하는 알고리듬이 이상(理想)!
    BUT! 두 기준은 서로 상충하는 경우가 많다. 즉, 메모리 사용량을 희생해 속도를 높이거나, 속도를 희생해서 메모리 사용량을 줄여인 알고리듬들을 훨씬 자주 볼 것이다.

시간복잡도 분석(Time complexity)

알고리듬의 수행 속도를 측정하는 방법
1. 프로그램의 수행 시간을 측정(Timer)
 -> 가장 직관적인 방법이지만 하드웨어, 사용 언어, 운영체제 등 외부 요소가 시간에 영향을 미치므로 부적합!

2. 수행 시간 기준 기본적인 연산의 수 비교 (ex. 사칙연산, 대소비교, 대입연산)
 -> 가장 깊이 중첩된 반복문의 내부에 있는 기본적 연산들은 더 쪼갤 수 없기 떄문에, 이것이 시간 복잡도의 대략적인 기준이 된다.

※ '시간 복잡도가 높다'는 말은 입력의 크기가 증가할 때, 알고리즘의 수행속도가 더 빠르게 증가한다는 의미이다.
※ 입력 크기가 큰 것을 가정하기 때문에 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다.

입력 종류에 따른 수행시간에 변화
 입력 종류에 따라 수행 시간이 달라지는 경우를 고려하기 위해 우리는 최선, 최악의 경우 그리고 평균적인 경우에 대한 수행 시간을 각각 따로 계산해야한다.
-> 전산학은 상한의 중요한 초점을 맞추기 때문에 최악의 경우에 관심사가 많다.

Big-O(점근적 시간 표기)
모든 연산 수를 세는 것은 비효율적! 그래서 가장 깊이 중첩된 반복문만을 고려했던 것처럼 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려!
즉, 함수의 상한을 의미
※ Big-O 예시) 상수시간-O(1), 로그시간-O(log n), 2차 다항시간-O(n2)
-> 대부분 알고리듬문제의 답은 2차 다항시간보다 크지 않다!