빅오 표기법(big-O notation) 정복하기

 

# 1. 빅오 표기법이란?

 

빅오 표기법(Big-O Notation)은 알고리즘의 실행 시간 복잡도를 분석하는 수학적 표기법으로,

input의 크기가 무한하게 증가할 때 실행 시간을 나타내는데 사용됩니다.

즉, 알고리즘 성능평가를 위한 강력한 도구가 빅오 표기법입니다.

 

Big-O 표기 방법 : O(n)

 

이때 괄호 안의 값은 입력 데이터의 크기에 대한 함수로, 알고리즘의 시간 복잡도 또는 공간 복잡도를 나타냅니다.

ex) O(1), O(n), O(log n) ...

 

 

 

 

#2. 간단한 예시로 알아보자

def get_first_element(inputs):
    return inputs[0]

 

간단한 예시로 위와 같이 List를 input으로 받아오는 함수가 있다고 가정해봅니다.

여기서 함수는 "2번"의 연산이 있게 되는데,

1. inputs list의 첫번째 원소에 접근

2. 접근한 원소를 반환

 

그렇다면 2번의 연신이 있으니 이 함수의 시간 복잡도는 O(2)일까요?

당연하게도 아닙니다.

위 함수의 복잡도는 O(1) 인데요.

 

빅오표기법에는 큰 2가지 특징이 있습니다.

1. 상수항 무시

2. 최고차항만 의미를 갖음

3. 최고차항의 계수는 의미가 없음

 

그 이유는 알고리즘의 효율성은 입력값의 크기에 따라 영향을 받게 되는데,

빅오의 경우 입력값이 무한하다는 가정에서의 알고리즘의 효율성을 평가하므로

상수항과 같이 사소한 부분은 무시하게 됩니다.

 

def linear_search(inputs, target):
    for i in range(len(inputs)):
        if inputs[i] == target:
            return i
    return -1

 

또 다른 예시로 inputs 데이터에서 target 데이터와 같은 경우 데이터의 위치를 return 하는 함수가 있다고 가정해봅니다.

이 경우 inputs 데이터가 n개라고 한다면,

 

위 연산의 경우 연산 횟수가 "2n + 상수(자잘한연산)" 로 표현할 수 있을 것입니다.

1. n : 리스트 inputs의 i번째 원소에 접근하는 연산 

2. n : inputs[i] == target: 두 값을 비교하는 연산

3. 상수 : 그외 자잘하게 데이터를 가져오거나 반환하는 연산

 

빅오 표기법(Big-O Notation)으로 표현할때에는 입력 값이 무한할 때를 상정하므로 상수는 무시한다면 "2n"이 남게 되고,

최고차항의 계수는 의미가 없다는 특징을 본다면 "n"이 남게 되므로,

 

위 함수의 시간복잡도는 O(n) 이됩니다.

O(n)의 의미로는 입력크기에 따라 시간복잡도가 선형적으로 증가함을 의미합니다.

 

또다른 예시를 본다면

def linear_search(inputs):
    n = 0
    for i in range(len(inputs)):
        for j in range(len(inputs)):
            n = n + 1
            print("감사합니다")

 

input size 만큼 반복하는 반복문에 또 input size 만큼 반복 하는 이중 반복문이므로 

자잘한 상수들을 무시하고 연산횟수는 아래와 같이 표현할 수 있게됩니다.

$n^2$ : 리스트 inputs의 i번째 원소에 접근한 후 inputs의 j번째 원소에 접근하는 연산

 

그렇다면 위 함수의 시간 복잡도는 $O(n^2)$ 라고 할 수 있겠습니다.

 

 

 

#3. 시간복잡도 효율비교

시간복잡도 효율순은 아래와 같습니다.

$$O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(2^n) < O(n!)$$

 

알고리즘의 종류와 구현 방식에 따라 빅오 표기법이 다르고, 

같은 기능을 하는 코드라도 구현 방식과 효율성에 따라 더 좋거나 낮은 효율성을 보이기도 합니다.

 

 

 

 

#4. 다양한 표기법

 

Big-O 표기법의 경우 입력데이터가 증가함에 따라 최악의 경우의 시간 복잡도를 나타냅니다.

가령 특정 배열에서 하나의 수를 찾아내는 알고리즘이 있다면 최악의 수는

1. 찾고자 하는 수가 없는 경우

2. 찾고자 하는 수가 배열의 마지막에 있는 경우

가 될 수 있겠습니다.

 

다른 표기법을 살펴본다면,

 

1. Big-O(빅-오)

• 알고리즘의 최악의 경우 (worst-case) 시간 복잡도

• 알고리즘의 성능 상한을 분석하는 데 사용

• O(n), O(n^2)

 

2. Big-Ω (빅-오메가)

• 알고리즘의 최선의 경우 (best-case) 시간 복잡도

• 알고리즘의 성능 하한을 분석하는 데 사용

• Ω(1), Ω(n), Ω(log n)

 

3. Big-Θ (빅-세타)

• 알고리즘의 평균적인 경우 (average-case) 시간 복잡도

• 알고리즘의 전반적인 성능을 분석하는 데 사용

• Θ(n), Θ(n^2)