알고리즘 시간 복잡도 계산하기: Big-O 표기법

시간 복잡도: Big-O 표기법

 

알고리즘의 효율성을 이론적으로 분석하는 방법으로,

Big-O 표기법은 불필요한 연산을 제거하여 시간 복잡도를 간단히 나타낸다.

 

시간 복잡도

입력값과 연산 수행 시간의 상관관계를 나타내는 척도

 

시간 복잡도 분석

• 시간 복잡도 분석에서는 알고리즘이 수행하는 연산의 횟수를 계산한다.
• 입력의 개수가 증가함에 따라 연산의 횟수가 어떤 형태로 증가하는지에 관심을 둔다.

 

시간 복잡도 함수

알고리즘이 수행하는 연산의 횟수를 나타내는 함수이다. 입력의 개수 n에 대한 함수(T(n))으로 표현한다.

 

n²을 구하는 문제에 대한 3가지 알고리즘이 다음과 같을때,

def Algorithm_A<(n):
    sum = n*n

def Algorithm_B(n):
    for i in range(n):
        sum += n

def Algorithm_C(n):
    for i in range(n)
        for j in range(n)
            sum += sum

 

시간 복잡도 함수에서는 n번 반복되는 연산은 n으로, n의 개수와 상관 없이 일어나는 연산은 상수 1로 나타낸다.

# Algorithm_A
곱셈연산: n*n # 1
대입연산: sum <- n*n # 1
--> 곱셉연산 1 + 대입연산 1
--> T_A(n)=2

# Algorithm_B
덧셈연산: sum+n # n
대입연산: {
            i <- (1 to n)        # n,
            sum <- sum+n    # 1
           }
--> 대입연산 n+1 + 덧셈연산 n
--> T_B(n)=2n+1

# Algorithm_C
덧셈연산: sum+1 # (n^2)
대입연산: {
            i <- (1 to n)         # n, 
            j <- (1 to n)         # (n^2), 
            sum <- sum+1     # 1
           }
--> 대입연산 (n^2)+n+1 + 덧셈연산 n^2
--> T_C(n)=2(n^2)+n+1

 

각각의 시간 복잡도 함수를 그래프로 살펴보면 연산 증가 속도의 확연한 차이를 확인할 수 있다.

 

 

점근적(Asymptotic) 표기

점근적 표기는 입력의 크기 n이 무한대로 커질 때 복잡도를 간단히 표현하기 위해 사용한다.

 

"정확히 몇 번"의 연산이 이루어지는지가 아닌,

"무엇에 비례하는" 연산이 이루어지는지에 관심을 두고

시간 복잡도 함수의 최고 차항만을 계수 없이 단순화하여 사용한다.

 -->  1                       O(1)      > 상수
 -->  3n + 1                O(n)      > n이 가장 큰영향을 미친다.
 -->  2n^2 + n + 1       O(n^2)   > n^2이 가장 큰영향을 미친다.

 

점근적 표기의 종류

빅오(Big-O)

• 복잡도 함수의 상한
• 입력 구성이 알고리즘 실행 시간을 가장 많이 요구하는 경우
• 가장 중요하게 사용됨

빅오메가(Big-Ω)

• 복잡도 함수의 하한
• 실행시간이 가장 적은경우로 큰 의미가 없다

빅세타(Big-θ)

• 복잡도 함수의 평균
• 알고리즘의 모든 입력을 고려하고 각 입력이 발생할 확률을 고려한 평균적 실행시간
• 평균에 대한 가정이 어려움

 

자주 사용되는 빅오(Big-O) 표기

 

O(1): 상수형

• 문제 해결을 위해 입력 n과 관계 없이 항상 일정한 단계를 수행함

 

O(logn):로그형

• 문제 해결을 위한 단계들이 입력 n에 따라 특정 요인에 의해 줄어듬

 

O(n):선형

• 문제 해결을 위한 단계와 입력 n이 선형적인 1:1 관계를 가짐
• ex) 반복문이 한번 있을 때

 

O(nlogn): 선형로그형

• 문제 해결을 위해 n*(log₂n) 번의 단계가 필요함

 

O(n²): 2차형

• 문제 해결을 위해 입력 n의 제곱 번의 단계가 필요함
• ex) 반복문이 두번 있을 때

 

O(n^k): k차형

• 문제 해결을 위해 입력 n의 상수 k 제곱 번의 단계가 필요함

 

O(kⁿ): 지수형

• 문제 해결을 위해 주어진 상수 k의 n제곱 번의 단계가 필요함

 

O(n!): 팩토리얼형

• 문제 해결을 위해 n! 번의 단계가 필요함

 

ㅊ

 

<참고>

- https://blog.chulgil.me/algorithm/