시간 복잡도

요약

내용

특징

• 알고리즘이 실행되는데 걸리는 시간을 입력 크기n에 따라 분석하는 척도이다.
• 알고리즘의 입력 크기(n)에 따라서 얼마나 많은 시간이 필요한지 분석하여, 시간 효율성을 평가할 수 있다.
• 빅오 표기법, Bing-O Notation을 이용하여 최악의 경우 얼마나 걸리는지를 나타낸다.

계산 방법

1. 연산 횟수 분석
   • 알고리즘 내에서 발생하는 반복문, 조건문, 함수 호출 등을 각 코드의 실행 횟수로 계산한다.
   • 각 연산이 입력 크기 n에 따라 몇 번 실행되는지 세어본다.
2. 가장 영향력 있는 항만 남기기
   • 반복문을 발생하는 연산 횟수를 입력 크기 n에 대해 수식으로 나타낸 후, 가장 높은 참수의 항만 남기고 나머지는 무시한다.
   • 5n^2 +3n +2는 O(n^2)이다.

예시

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

• 이진 탐색은 검색 범위를 절반씩 줄여나가는 방식으로, 배열을 탐색할 때 마다 범위가 절반으로 줄어든다.
• n에서 절반씩 줄어들어 n,n/2,n/4,…,1 형태로 탐색이 진행된다.
• 따라서 O(log n)이다.

참고