[CS] 빅오(Big-O) 표기법

점근 표기법 : 빅오(O), 오메가(Ω) , 세타 (Θ)

• Big-O Notation O(n): 최악의 경우
• Big-Theta Notation Θ(n): 평균의 경우
• Big-Omega Notation Ω(n): 최상의 경우

 

• 알고리즘 시간복잡도 표기 시 빅오 표기법을 사용하는 이유
  • 빅오 표기법이 알고리즘 효율성을 상한선 기준으로 표기
    • → 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미
  • 빅오메가는 하한선을 기준→ 사실상 의미 X
  • 빅세타는 상한선과 하한선의 사이를 기준→ 평균정도의 의미로 사용

 

빅오(Big-O) 표기법

• 알고리즘의 효율성을 표기해주는 표기법
  • 이때 알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미
• 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용
  • 시간 복잡도: 알고리즘 실행 속도
  • 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

 

• 효율성
  • 왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.
  • 상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수

faster  O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N)   slower 

 

 

 

 

 

• 계산 방법
  1. 계수 버리기
     • O(2N) → O(N)
  2. 식의 차수/우세한 항을 이용하기
     • O(n + n log n) → O(n)
     • O(100n100 + 10*2n) →  O(2n)
  3. 덧셈 vs 곱셈
     • 한 실행문을 하고 다음 실행문을 하는 경우: 덧셈을 이용
       • ex) for문 2번 : O(N+N) → O(N)
     • 실행문 안에 실행문이 있는 경우: 곱셈 이용
       •  ex) 2중 for문 : O(N*N) → O(N^2)
  4. 로그 런타임(log N)
     • 로그로 표현되는 알고리즘들은 대부분 문제가 반토막이 나는 경우
     • Binary Search와 같이 문제의 크기가 계속 절반으로 작아지는 경우 O(log N)으로 표현

 

 

---

출처

https://noahlogs.tistory.com/27 [인생의 로그캣]

https://codingpark.tistory.com/34