[ALGORITHM] 05. O(n²)

O(n²)은 입력 크기 n에 대해 제곱 비례하는 시간 복잡도를 가지는 알고리즘을 나타낸다.

즉, 입력 크기가 증가함에 따라 실행 시간이 제곱으로 증가하며 이는 일반적으로 중첩된 반복문이 있는 경우 발생한다.

O(n²)의 시간 복잡도를 갖는 알고리즘의 예시로는 다음과 같은 이중 반복문이 있다.

 

void bubble_sort(int data[], int n) {

     for (int i = (n - 1); i > 0; i--) { //이중 for 반복문 내부 문장이 ½n(n - 1)번 실행 : O(n)
     
         for (int j = 0; j < i; j++) {
         
             if (data[j] > data[j + 1]) {
         
                 swap(data[j], data[j + 1]);
             }
             
         }
     }
}