BigO 표기법은 최악의 경우에 나타나는 수행시간을 계수 생략하고 최고차항만으로 간단하게 표기하는 방식이다.
T1, T2는 각각 2n, 4n이므로 BigO로 표기하면 T1(n) = O(n), T2(n) = O(n)이고,
T3는 최고차항이 3/2 * n^2 이므로 BigO로 표기하면 T3(n) = O(n^2) 이다.
예2를 보면 n에 곱하는 상수값은 어차피 입력에 따라 달라지므로 고려하지 않아도 된다.
n은 count가 증가할수록 2의 배수로 나눠지기 때문에 등식을 써보면 log식이 나오는데, 1 count 동안 일어나는 연산횟수이므로 시간복잡도를 로그로 나타낼 수 있다.
공부일기