알고리즘의 자원 사용량을 분석
자원이란?
실행 시간, 메모리, 저장장치, 통신 등
실행시간의 분석에 대해서 다룸
실행 시간은 실행 환경에 따라 달라짐
-> 하드웨어, 운영체제, 언어, 컴파일러 등
실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트
연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현
데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐
-> 최악의 경우 시간복잡도: 검색 알고리즘에서 첫번째에 바로 검색 성공할 수도 있고 더 늦게 성공할 수도 있음
-> 평균 시간복잡도: 간단한 케이스에서는 평균 시간복잡도를 사용하지만 복잡한 케이스에서는 보통 최악의 경우 시간복잡도를 사용
점근적 표기법을 사용
유일한 분석법도 아니고 가장 좋은 분석법도 아님