파이썬 처리 시간 정리

알고리즘의 효율

복잡도의 접근적 표기

• 시간 복잡도는 입력 크기에 대한 함수로 표기하는데, 이 함수는 주로 여러 개의 항을 가지는 다항식이다.
• 이를 단순한 함수로 표현하기 위해 점근적 표기(Asymptotic Notation)을 사용한다.
• 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다
  • $O(Big-Oh)-$표기
  • $(Big-Omega)-$표기
  • $(Big-Theta)-$표기

$O(Big-Oh)-$표기

• O-표기는 복잡도의 점근적 상한을 나타낸다.
• 복잡도가 $f(n) = 2n^2-7n+4$이라면, $f(n)$의 $O-$표기는 $O(n^2)$이다.
• 먼저 $f(n)$의 단순화된 표현은 $n^2$이다.
• 단순화된 함수 $n^2$에 임의의 상수 c를 곱한 $cn^2$이 $n$이 증가함에 따라 $f(n)$의 상한이 된다. (단, c>0)
• 단순히 실행시간이 $n^2$에 비례하는 알고리즘

• 복잡도 f(n)과 O-표기를 그래프로 나타내고 있다.
• n이 증가함에 따라 $O(g(n))$이 점근적 상한이라는 것 (즉, $g(n)$이 $n_0$보다 큰 모든 n에 대해서 항상 $f(n)$보다 크다는 것)을 보여 준다.

$(Big-Omega)-$표기

• 복잡도의 점근적 하한을 의미한다.
• $f(n) = 2n^2-7n+4$의 Omega-표기는 $Omega(n^2)$이다.
• $f(n)=Omega(n^2)$은 ‘n이 증가함에 따라 $2n^2-7n+4$이 $cn^2$보다 작을 수 없다.
• O-표기 때와 마찬가지로 $Omega-$표기도 복잡도 다항식의 최고차항만 계수 없이 취하면 된다.
• 최소한 이만한 시간은 걸린다.

$(Theta)-$표기

• $O-$표기와 $Omega-$표기가 같은 경우에 사용한다.
• $f(n) = 2n^2+8n+3=O(n^2)=Omega(n^2)$이므로, $f(n)=theta(n^2)$이다.
• $f(n)$은 $n$이 증가함에 따라 $n^2$과 동일한 증가율을 가진다

자주 사용하는 O-표기

$O(1)$	상수 시간(Constant time)
$O(logn)$	로그(대수) 시간(Logarithmic time)
$O(n)$	선형 시간(Linear time)
$O(n logn)$	로그 선형 시간(Log-linear time)
$O(n^2)$	제곱 시간(Quadratic time)
$O(n^3)$	세제곱 시간(Cubic time)
$O(2^n)$	지수 시간(Exponential time)