[자료구조](1)[점근 표기법]

점근 표기법: 알고리즘의 시간/공간 복잡도를 입력 데이터 크기 N에 대해 표기하는 방법

• 아주 큰 N에 대해 고려 (N->무한)
• 가장 영향을 많이 주는 것만 고려
  예) x^2+100x -> x^2
• 상수나 계수는 무시
  5x -> x

종류

• Big-O (가장 최악의 경우): 가장 많이 쓰는 표기법
• Big-Ω (가장 최고의 경우)
• Big-Θ: (Big-O == Big-Ω)

수학적 정의

• Big-O
  임의의 함수 f(n)에 대해 양의 상수 c와 n0에 대해
  f(n)<=cg(n) (단, 모든 n에 대해 n>=n0) 이런 c, n0이 존재한다면
  이때 f(n)은 O(g(n))의 복잡도를 가진다.
  -> 즉, 일정 수준 이상에서 항상 f(n)보다 더 큰 g(n)을 찾는 것!
  
  예) f(n) = 3n^2+n+100일때, 4n^2만 되어도 n0= 10.6 근처 이후로 4n^2이 계속 크다.
  따라서 g(n) = n^2
  따라서 f(n)은 O(n^2)이다.
• Big-Ω
  임의의 함수 f(n)에 대해 양의 상수 c와 n0에 대해
  f(n)>=cg(n) (단, 모든 n에 대해 n>=n0) 이런 c, n0이 존재한다면
  이때 f(n)은 Ω(g(n))의 복잡도를 가진다.
  -> 즉, 일정 수준 이상에서 항상 f(n)보다 더 작은 g(n)을 찾는 것!
  
  예) f(n) = 3n^2+n+100일때, 3n^2이면 n0= 0부터 항상 g(n)이 f(n)보다 작다
  따라서 g(n) = n^2
  따라서 f(n)은 Ω(n^2)이다.
• Big-Θ
  예) f(n) = 3n^2+n+100일때, 4n^2만 되어도 n0= 10.6 근처 이후로 4n^2이 계속 크고 3n^2이면 n0= 0부터 항상 g(n)이 f(n)보다 작다.
  따라서 g(n) = n^2
  따라서 f(n)은 Θ(n^2)이다.
  
  임의의 함수 f(n)에 대해 양의 상수 c1, c2와 n0에 대해
  c1g(n)<=f(n)<=c2g(n) (단, 모든 n에 대해 n>=n0) 이런 c1, c2, n0이 존재한다면
  이때 f(n)은 Θ(g(n))의 복잡도를 가진다.예) f(n)이 n=홀수이면 n^2, n=짝수이면 n+4라면,
  각각 O(n^2), Ω(n), Θ(없음)

-> 특히 점근 표기법에서 g(n)은 무한정 커지거나 작아질 수 있으나 "상식적인" 선에서 표기하도록 한다.

 

Big-O의 예

• 상수: O(1)
  입력이 무엇이든 "hello"만 출력하는 함수
• 로그: O(logn)
  이진 탐색법 (N개를 2부분으로 나누며 탐색)
  -> N/(2^n) = 1(탐색 완료) -> n = log2N
• 선형: O(n)
  입력받은 N개의 데이터를 출력하는 함수
• 로그선형: O(nlogn)
  merge sort
• 제곱: O(n^2)
  이중 반복문
• 지수: O(2^n): 최악...