시간 복잡도 개념 및 설명

복잡도 분석

 

알고리즘의 효율

공간적 효율성과 시간적 효율성

• 공간적 효율성 : 연산량 대비 얼마나 적은 메모리 공간을 요하는 가
• 시간적 효율성 : 연산량 대비 얼마나 적은 시간을 요하는 가
• 효율성을 뒤집어 표현하면 복잡도(Complexity)
• 복잡도가 높을수록 효율성은 저하

 

시간적 복잡도 분석

• 하드웨어 환경에 따라 처리시간이 상이
  • 부동소수 처리 프로세서 존재유므, 나눗셈 가속기능 유무
  • 입출력 장비의 성능, 공유 여부

• 소프트웨어 환경에 따라 처리시간이 상이
  • 프로그램 언어의 종류
  • 운영체제, 컴파일러의 종류

• 이러한 환경적 차이로 인해 분석이 난해

 

복잡도의 점근적 표기

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

 

O(Big - Oh) - 표기

• 복잡도의 점근적 상향을 나타냄

 

• 단순화된 함수 n^2에 임의의 상수 c를 곱한 cn^2이 n이 증가함에 따라 f(n)의 상한이 된다. (단, c > 0)

• 단순히 "실행시간이 n^2에 비례"한다는 의미를 갖는다.

 

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

 

Ω(Big - Omega) - 표기

• 복잡도의 점근적 하한을 의미

 

• n이 증가함에 따라 f(n)이 cn^2 보다 작을 수 없다는 의미이다. 이때 상수 c=1로 간주한다.
• O-표기와 마찬가지로, Ω-표기도 복잡도 다항식의 최고차항만 계수 없이 취하면 된다.

• 최소한 "이만큼의 시간이 소요"된다라는 의미를 갖는다.

 

• 복잡도 f(n)과 Ω-표기를 그래프로 나타내면 다음과 같다.
• n이 증가함에 따라 Ω(g(n))이 점근적 하한이라는 것을 보여준다.
  • g(n)이 n0보다 큰 모든 n에 대해서 항상 f(n)보다 작다.

 

θ(Theta) - 표기

• O-표기와 Ω-표기가 같은 경우에 사용

 

• f(n)은 n이 증가함에 따라 "n^2과 동일한 증가율을 갖는다"라는 의미이다.

 

자주 사용한는 O-표기

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

• 효율적인 알고리즘의 필요성
  • 10억 개의 숫자를 정렬하는데 O(n^2) 알고리즘은 300여 년이 걸리는 반면에 O(nlogn) 알고리즘은 5분 만에 정렬한다.
  • 효율적인 알고리즘은 슈퍼컴퓨터보다 더 큰 가치가 있음