제 7장: 알고리즘의 계산량(3)

74. 알고리즘의 계산량 → O(빅-오) 표기법

• 알고리즘 계산량의 일반적 표기법 → O(빅-오) 표기법
• 측정 대상 알고리즘의 계산량을 처리하는 데이터 개수 n을 기준으로 표기
• 예시: n개 데이터 계산량이 n에 비례 → O(n) 으로 표기
• 예시 2: 1~N까지의 합을 하나하나 더해 계산 → N이 무한대일 경우 N의 계수 3과 +3 영향이 거의 사라짐 → 계산량: O(n)
• 예시 3: 1~N까지의 합을 N(N+1)/2 로 계산 → 데이터 개수에 의존하지 않고 계산량 항상 3 → N에 의존하지 않는 계산량 = O(1)
• 예시 4: 버블 정렬 → N 값이 커짐에 따라 N 값에 의존하는 이중루프(반복 안 반복) 처리 → N * N 번 작업 → 계산량 = $O(n^2)$
• 예시 5: 이진 검색(바이너리 서치) → 1번째 탐색 범위가 N일경우 1번 조작 시 검색범위 1/2로 좁혀짐 → 반복 횟수가 k일 경우 $N*\frac{1}{2}^k=1$ → 해당 식 변형 시 $2^k$ = N → k = $log_2n$ → 계산량 = $O(log_2n)$
• 계산량의 대소관계: O(1) < $O(log_2n)$ < O(n) < $O(n * log_2n)$ < $O(n^2)$ < $O(2^n)$