Chapter 1-1. Big-O 표기법

인프런에 있는 Rookiss님의 강의 Part2: 자료구조와 알고리즘 를 듣고 정리한 필기입니다. 😀

🔔 Big-O 표기법

사용하는 이유

• Big-O 표기법
  • 알고리즘의 성능을 객관적으로 측정하기 위하여 사용.
    • 단순히 실행 속도를 비교하는 것으로 알고리즘 성능을 측정하는건 컴퓨터 실행 환경에 따라 차이가 있기 때문에 별로 좋지 못하다.
    • 입력이 적은 구간과 많은 구간에서 성능이 확연히 차이가 나는 경우도 있을 수 있다.

표기법

1단계 : 수행 연산의 개수를 대략적으로 판단

수행되는 연산의 개수를 대략적으로 판단한다.

• 어떤 연산이 1 개만 있다면 1 개
• 어떤 연산이 N 번 도는 for문 안에 있다면 N 개
• 어떤 연산이 N 번 도는 이중 for문 안에 있다면 N^2 개

2단계 : 대장만 남긴다.

public int Add(int N)
{
    int sum = 0;   //  1 번

    for (int i = 0; i < N; i++)  // N 번
        sum += i;
    
    for (int i = 0; i < 2 * N; i++)  // 4 * N^2 번 ⭐⭐ 얘가 가장 영향력이 크다. N^2니까.
      for (int j = 0; j < 2 * N; j++) 
          sum += 5;
    
    sum += 1234567;   // 1 번

    return sum;
}

1. 영향력이 가장 큰 대표적인 연산만 남긴다.
   • O(1 + N + 4 * \(N^2\) + 1) = O(4 * \(N^2\))
   • 가장 영향력이 큰 4 * \(N^2\) 번 연산만 남긴다.
2. 상수는 무시한다.
   • O(4 * \(N^2\)) = O(\(N^2\))
   • 위 코드의 성능은 최종적으로 O(\(N^2\)) 라고 할 수 있다.
     • cf) O는 Order Of라고 읽는다.

거시적인 관점에서 보면, N 이 무한으로 커지면 커질 수록 N 과 \(N^2\)의 차이는 매우 커지게 된다. 따라서 대표적인 연산만 남기고 더 작은 연산들은 무시하는 것.

• 이차함수가 일차함수보다 같은 N 이라도 이차 함수가 증가폭이 훨씬 더 크니까..!

크기 순서

• N은 데이터(입력)의 크기가 된다.
• O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)
  • 👉 작을 수록 연산이 적게 걸린다는 것이니 가장 좋은 알고리즘이라는 뜻!
  • O(N)까지는 보통 무리가 없다고 얘기한다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기