[알고리즘] 시간복잡도와 Big-O 표기법
알고리즘 강의를 수강할때 작성한 강의 노트를 기반으로 포스팅합니다. 1. 알고리즘의 분석과 수행시간 알고리즘의 분석: 알고리즘을 실행하는데 필요한 자원을 예측하는 것 메모리, 통신대역, 하드웨어와 같은 자원이 측정의 관심대상이 되기도 하지만 대부분의 경우 측정대상은 계산시간이다. 수행시간: 기본연산개수 또는 실행된 단계의 횟수 (즉, 알고리즘의 수행시간은 각 명령문 수행시간의 합이다.) 주어진 문제의 입력크기가 다양하기 때문에 최악, 최상, 평균적인 경우 총 3개의 case를 가질 수 있는데 우리는 최악의 경우에 주로 관심을 둘 것이다. (모든 입력에 대한 수행시간의 상한이 되며 이보다 더 나쁜 경우는 존재하지 않기 때문에, 그리고 최악의 경우가 빈번하기도 함) 2. 시간복잡도 증가차수, 점근적 효율성을..
