[Programming] Big O Notation(빅오 표기법): O(n^2) Example Codes

Big O Notation(빅오 표기법): O(n^2) Example Codes

---

# 포스트 난이도: HOO_Middle

https://whoishoo.tistory.com/notice/161

[Notice] 포스트 난이도에 대한 설명

---

Big O Notation 중에서 n^2에 대한 예제 코드를 살펴보도록 하겠다.

n^2 코드는 기본적으로 nest for문 형태로 구성되어 있으며, n*n이 적용되어 n^2이 된다.

만약에 반복되는 기준값(또는 범위 값)이 다른 경우에는 n*m이 된다.

어렵게 생각할 필요 없이 같은 범위 값이 반복문 안에 반복문이 또 있어서 n^2이 된다고 생각하면 된다.

아래 예제 코드를 살펴보면 이해가 쉽다.

O(n^2)의 대한 C, C++, Python 등의 부분 코드를 아래에 작성해놓았다.

해당 코드들은 실행이 바로 가능한 형태가 아닌 O(n^2) 부분을 보여주기 위한 부분 코드이다.

전체 실행 바로 가능한 예제 코드가 필요하다면 필자에게 얘기하면 추가적으로 포스팅을 하겠다.

---

# C: O(n^2)

void exampleCodes(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d = %d\n", arr[i], arr[j]);
        }
     }
}

---

# C++: O(n^2)

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a = a + j;
        }   
    }

---

# Python: O(n^2)

for i in range(0, n):
   for j in range (0, n):
       print(j)

---

# In conclusion, 3줄 요약

1. O(n^2)은 언어마다 작성 방법은 다르지만 방식은 같다.

2. O(n^2)이 어떤식으로 작성되는지 알아야 응용이 가능하다.

3. O(n^2)에 대해서 완벽히 이해하자.

---