[알고리즘] 점근 표기법과, 빅 오로 시간복잡도 계산하는 법

 

---

1. 점근 표기법(Asymptotic Notation)

: 시간복잡도를 근사치로 표현한 것입니다. 아래에서 빅 오를 예시로 들어 어떤 식으로 시간복잡도를 계산하는지에 대해 알아볼건데, 컴퓨터의 성능과는 관계없이 두 알고리즘을 비교해서 어떤 알고리즘이 더 나은 알고리즘인지, 더 빠른 알고리즘인지를 가늠할 때 사용합니다.

 

---

2. 점근 표기법의 종류

1) 빅 오 (Big O : Ο) : 알고리즘이 최악으로 실행될 경우(아무리 늦더라도 이 정도의 성능을 보장한다는 것을 의미)의 성능을 표현할 때 사용. 

알고리즘의 성능을 표현하는데 가장 많이 사용. = 최악의 경우의 수에 어떤 성능을 내는지 궁금해하기 때문.

 

2) 빅 오메가 (Big Omega : Ω) : 알고리즘이 가장 최선으로 실행될 경우의 성능을 표시.

 

3) 빅 세타 (Big Theta : Θ) : 알고리즘 성능의 상한(Ο표기법)과 하한(Ω 표기법)을 동시에 나타내는데 사용. 평균적인 경우에서의 시간복잡도 이므로 빅 오, 빅 오메가 표기법보다 정확.

 

---

3. 빅 오(Big O)로 시간복잡도 계산하는 방법

하나의 문제를 푸는 알고리즘은 다양합니다. 그 중 어느 알고리즘의 실행 속도가 더 빠른지를 알기 위해 시간 복잡도를 계산하는 것입니다.

시간 복잡도는 사실상 반복문이 얼마나 들어갔느냐가 좌우합니다.

n을 입력했을 때의 시간 복잡도 함수는 아래와 같이 표시합니다. 

O(1) < O(𝑙𝑜𝑔𝑛logn) < O(n) < O(n𝑙𝑜𝑔𝑛logn) < O(𝑛2n2) < O(2𝑛2n) < O(n!)

(어떤 시간 복잡도가 더 실행 속도가 오래 걸리는지 크기 비교)

 

 

코드 예시와 시간 복잡도를 어떻게 표시하는지에 대한 예시를 보여드리겠습니다.

//숫자 n이 몇이든 코드 한 줄만 읽기 때문에 O(1)로 표기합니다.
if(n > 100) Debug.Log(n);

//반복문으로 인해 n번의 코드를 읽기 때문에 O(n)으로 표기합니다.
for (int i = 0; i < n; i++) 
{
    Debug.Log(n);
}

//그렇다면 위의 반복문을 2번 반복되게 한다면?
//반복문으로 인해 n번의 코드를 2번 읽기 때문에 O(2n)으로 표기합니다.
for (int i = 0; i < 2; i++) 
{
    for (int i = 0; i < n; i++) 
    {
        Debug.Log(n);
    }
}

//반복문을 n번 반복한다면?
//O(𝑛^2)으로 표기합니다.
for (int i = 0; i < n; i++) 
{
    for (int i = 0; i < n; i++) 
    {
        Debug.Log(n);
    }
}

 

 

위의 예시들에서 감이 오셨나요?

또 다른 간단한 예시를 들어보겠습니다.

1부터 n 까지의 합을 구하는 알고리즘이 필요한 상황입니다. 아래 두가지 알고리즘의 시간복잡도를 비교해보도록 하겠습니다.

1.
int total = n * (n + 1) / 2;


2.
int total = 0;
for (int i = 1; i < n; i++) 
{
    total += n;
}

1번은 공식을 이용해 답을 도출했으며, n의 값이 크든 작든 코드 한 줄만 읽으므로 O(1)로 표기합니다.

2번은 1부터 n까지의 수를 정직하게 더했으며, n만큼 코드가 반복되므로 O(n)으로 표기합니다.

 

두 시간복잡도를 비교했을 때 O(n) > O(1) 이므로 1번 알고리즘을 사용하는게 알고리즘의 실행속도가 더 빠르다는 것을 알 수 있습니다. 

---

4. 각 알고리즘에 따른 시간 복잡도 

---

출처

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=nsj6646&logNo=221511635919