3. 함수의 증가(1)
3. Growhth of Functions 일반적으로 알고리즘의 정확한 실행 시간을 계산할 필요가 없다. 입력이 충분히 크면 최고차항간 비교만 유의미하기 때문이다. ex) 병합정렬(nlgn), 삽입정렬(n^2) 처럼 이전에 공부한 애들을 보면 알 수 있음. 입력이 충분히 커서 실행 시간의 증가율의 상대적 순서만 볼때, 우리는 알고리즘의 점근적(asymptotic) 효율성을 따지게 된다. 입력 크기가 아주 작을 때를 제외하고는 일반적으로 최선의 선택이 될 수 있다. 즉, 일반적인 상황이란 최고차항의 차수로 실행시간의 차이를 비교하는 때를 말하는데 이 때는 점근적으로 접근하게 된다. ...