계산 시간을 표현하는 방법

지난 글: [알고리즘] - 계산 시간 구하는 법

 

지난 글에서 계산 시간을 구하는 법을 배웠었다. 이제 그 결과를 간략화하는 방법을 배워보자. Tc와 Ts는 기본 단위로 입력과는 무관하다. 입력에 의해 바뀌는 것은 수열의 길이인 n이므로 선택 정렬의 실행시간은 n을 크게하면 할수록 입력 수열의 크기 n의 2승만큼 비례해서 바뀐다. 알고리즘의 계산 시간 표시는 O(n의 제곱) 식으로 표기한다. 이를 보았을 때, O(n)과 O(n의 2승) 중 어느 것이 계산 시간이 더 짧은지를 알 수 있다.

 

솔직히 뭔말인지 모르겠다. 책에 수식이 첨부 되어있기는 하나 수랑 안친해서 잘 모르겠다. 아마 알고리즘은 오랜 시간을 들여 친해져야 할 것 같다.

 

참고 서적: