Big - O Notation

빅 - 오 표기법(worst case)

$f(x) ≤ C*g(x)$ → $f(n) = O(g(n))$

빅 - 오메가 표기법(best case)

$f(x) ≥ C*g(x)$ → $f(n) = Ω(g(n))$

빅 - 세타 표기법(avg case)

$f(n) = O(g(n))$ and $f(n) = Ω(g(n))$ is true → $f(n) = θ(g(n))$

Big - O Notation 특징

---

1. 상수항 무시

   $O(2n)$ → $O(n)$

   $n$값이 $∞$로 접근시 2의 영향력은 무시할정도

2. 영향력이 없는 항 무시

   $O(n^{2}+2n+1)$ → $O(n^{2})$

   $n$값이 $∞$로 접근시 $n^{2}$의 영향력에 비해 $2n+1$의 영향력 무시가능

Big - O Notation 성능

---

1. $O(1)$

   인덱스로 직접접근

   int arr[20] = {0};
   
   arr[10] = 10  // O(1)

2. $O(log$ $n)$

   이진트리구조, 횟수를 줄여나가는 반복문

   for (int i = n; i > 1; i /= 2) {  //O(log n)구조 
           printf("n = %d\n", i);
       }

3. $O(n)$

   단일 for문

   for(int i = 0 ; i < n ; i++){ //O(n)
   	arr[i] = i;
   }

4. $O(n$ $log$ $n$$)$

   퀵 정렬, 병합 정렬, 힙 정렬

      for (int i = 0; i < n; i++) {             //O(n)*
           for (int j = n; j > 1; j /= 2) {     //O(log n) => O(n log n)
               printf("i = %d, j = %d\n", i, j);
           }
       }

5. $O(n^{2})$

   이중 for문, 버블 정렬, 선택 정렬

   for(int i = 0 ; i < n ; i++){      //O(n)*
   	for(int j = 0 ; j < n ; j++){   //O(n) =>O(n^2)
   		arr[i][j] = i+j;
   	}
   }

6. $O(2^n)$

   재귀 피보나치 수열

   int fibonacci(int n) {
       if (n <= 1) {
           return n;  // n이 0 또는 1이면 바로 반환
       }
       // 두 개의 분기로 나눠서 계산 (2씩 곱해짐)
       return fibonacci(n - 1) + fibonacci(n - 2);   //O(2^n)
   }
   

Big - O 표기간의 성능비교

$O(n^{2}+2n)$ 와 $O(2^n+3^n)$간의 성능비교시 두표기법을 나눈뒤 로피탈정리를 이용해 비교하면 편리하다