data structure(자료 구조) - 점근적 분석, 점근 표기법::FBTT

이번에는 성능(효율)과 관련된 점근적 분석과 점근 표기법에 대해서 알아보겠습니다.

성능(효율)에 관한 설명은 이전에 한 적이 있는데요

 

https://readytoearndon.tistory.com/9?category=835876

data structure(자료 구조) - manipulation of data(자료의 관리)

 

간단히 말하면, 성과를 얻기 위해 투입되는 자원을 측정하는 것입니다.

컴퓨터에게 자원은 시간(CPU)과 공간(mamory)이 있습니다.

시간에 관련된 성능을 시간 복잡도, 공간에 관련된 성능을 공간 복잡도라고 합니다.

 

그러면 공간 복잡도와 시간 복잡도의 예를 들어보겠습니다.

①

sum = 0
n = int(input())
for i in range(n):
    num = int(input())
    sum += num
print(sum)

②

sum = 0
n = int(input())
num_list = []
for i in range(n):
    num_list.append(int(input()))
for i in range(0, len(num_list)):
    sum += num_list[i]
print(sum)

이 두 python 코드 모두 n개의 정수를 입력 받아 합을 구하는 프로그램입니다.

공간의 측면에서 보면 1번 코드는 n의 개수에 관계없이 항상 4개(sum, n, i, num)의 변수만이 사용됩니다.

반면 2번 코드는 list를 사용하여 n개의 정수가 입력되면 길이가 n인 list가 생성됩니다.

 

이제 배우게 될 표기법으로 나타내면 1번은 공간 복잡도가 O(1)이고 2번은 O(n)입니다.

 

시간의 관점에서 보면 1번, 2번 모두 n번 반복하게 됩니다. 시간 복잡도는 두 코드 모두 O(n)입니다.(2번은 2n이지만 그 이유는 뒤에)

 

점근적 분석법(asymptotic analysis)

성능은 입력의 크기에 따라 결정됩니다. 입력의 크기가 작으면 알고리즘의 효율과 상관없이 빨리 끝나게 됩니다. 문제는 입력의 크기가 아주 클 때 발생하게 됩니다.

그래서 점근적 분석법은 이 사항을 고려하여 입력의 크기가 충분히 클 때에 대해 분석하는 것을 가정합니다.

참고로 점근은 점근선의 점근과 같은 의미입니다.

 

유일한 분석법도아니고 가장 좋은 분석법도 아니지만 상대적으로 간단하고 실행 환경에 비의존적이라는 장점 덕분에 광범위하게 사용됩니다.

 

g(n)을 이용한 f(n)의 성능 표현

성능은 최악일 때를 표현하므로 f(n)을 어떤 프로그램의 성능이라고 할 때 g(n)은 항상 f(n)보다 커야합니다.(f(n) <= g(n))

g(n)은 f(n)의 최악

g(n)은 표준적인 함수를 사용합니다.

ex) 1, n, log n, n log n

 

점근 표기법

Big - O 표기법

정의 : f(n) is O(g(n)) as n -> ∞, if and only if ∃n0, ∃M > 0 such that f(n) <= Mg(n) for n0 < n

n0 < n : 충분히 큰 수에 대해 다루기 때문

M : 같은 비율로 증가하는 함수를 허용하기 위함

ex) n과 2n은 모두 n에 비례하여 증가

성질

1. 어떤 n > n0에 대해서 g1(n) < g2(n)이라면 f(n) = O(g1(n))은 f(n) = O(g2(n))이다.
2. 어떤 상수 k에 대해서 f(n) = O(kg(n))이라면, f(n) = O(g(n))이다.
3. f(n) = O(g1(n) + g2(n))이고, 어떤 n > n0에 대해서 g1(n) < g2(n)이라면 f(n) = O(g2(n))이다.

1번: f(n) <= g1(n) < g2(n) 이기 때문

ex) f(n) = O(n)이라면, f(n) = O(n ^ 2)

 

2번: kg(n) = Mg(n)이기 때문입니다. big - O표기법에서는 f(n) = O(kg(n)) 이런 식으로 잘 표기하지 않습니다.

ex) f(n) = O(2n)이라면, f(n) = O(n)

 

3번: g1(n) + g2(n) <= g2(n) + g2(n) = 2g2(n)이지만 2번 성질에 의해 f(n) = O(g2(n)) big - O표기법에서는 f(n) = O(g1(n) + g2(n)) 이런 식으로 잘 표기하지 않습니다.

ex) f(n) = O(n ^ 3 + n ^ 2)이라면 f(n) = O(n ^ 3)

 

저는 2번과 3번 같은 경우 이렇게 생각하고 있습니다. '어차피 점근적 분석은 충분히 큰 수에 대해 이루어지는 것이니 앞에 곱해져 있는 계수는 크게 영향을 미치지 않고 3번의 경우도 제곱항은 3제곱항에 비해 큰 영향을 끼치지 못하기 때문에 생략한다'라고 기억하고 있습니다.

 

big - Ω(omega) 표기법

big - Ω 표기법은 big - O표기법의 반대이다.

f(n)은 g(n)보다 빠르다 -> f(n) = O(g(n))

g(n)은 f(n)보다 느리다 ->g(n) = Ω(g(n))

 

big - Θ(theta) 표기법

big - Θ 표기법은 f(n)과 g(n)이 서로 big - O와 big - Ω표기를 만족할 때 사용할 수 있는 표기법이다.

f(n) = O(g(n)) and g(n) = Ω(f(n)) 이면 f(n) = Θ(g(n))

ex) f(n) = 2n^2 + 4n일 때, g(n) = n ^ 2 or g(n) = n^2 / 2이면 f(n) = Θ(g(n))