[Algorithm] 시간복잡도

목차

시간복잡도(time complexity)

시간복잡도분석을 하는이유?

시간복잡도의 표현방법

 

 

시간복잡도(time complexity)

컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도

 

 

시간복잡도분석을 하는이유?

실제 시간으로 알고리즘의 효율성을 비교하게 될경우 CPU와 같은 실제로 연산하는 컴퓨터의 성능은 다 다르고 사용하는 언어에 따른 차이가 있기 때문에 직접적으로 비교가 불가능하다.

따라서 알고리즘의 시간을 비교하기 위해서 컴퓨터성능,프로그래밍 언어등등의 차이를 제외하고 객관적인 측정법이 필요하였다.

일반적으로 알고리즘의 실행시간은 입력의 크기가 커질경우 증가하였고, 단위연산(basic operation)의 수행 횟수에 비례한다.

따라서 단위 연산이 수행되는 횟수와 입력의 크기로 알고리즘의 객관적인 효율성을 분석하기 위해서 사용된다.

 

시간복잡도의 표현방법

 분석 방법은 점근적 (Asymptotic)으로 점근적 분석 방법을 이용한 표기법이기 때문에 모아서 점근적 표기법으로 말하기도 한다.

1. 빅 오 표기법   Big-O  - O(n)

2. 오메가 표기법  Omega - Ω(n) (빅 오메가라고도함)

3. 세타 표기법   Theta -  Θ(n) (빅 세타라고도 함)

4. 리틀 오 표기법  Little-o - o(n)

 

 

1. 빅오 표기법 Big-O  - O(n) : 상한 표기법 (최악의 경우, worst case)

 

정의 

주어진 복잡도 함수g(n)에 대해서 O(g(n))는 정수n₀이상의 모든n에 대하여
f(n) ≤ c × g(n)이 성립하는 양의 실수 c와 음이 아닌 정수n₀이 존재하는 복잡도함수f(n)의 집합 

 

즉 , 점근적 상한선이다 

입력 크기가 무한대로 갈 때 점근적 상한이라는 뜻으로

아무리 나빠도 시간이 이보다 덜 걸린다. 즉, 최악의 경우를 나타낸다 ('기껏해야`, `최악')

f(n) = O(g(n))

 

2. 오메가 표기법  Omega - Ω(n)  : 하한 표기법 (최선의 경우, best case)

정의

주어진 복잡도 함수g(n)에 대해서Ω(g(n))는 정수n₀이상의 모든n에 대하여
f(n) ≥ c × g(n)이 성립하는 양의 실수 c와 음이 아닌 정수n₀이 존재하는 복잡도 함수 f(n)의 집합 

즉 , 점근적 하한선이다 

입력 크기가 무한대로 갈 때 점근적 상한이라는 뜻으로

최소 이만한 시간이 걸린다. 즉, 최선의 경우를 나타낸다 (' 적어도`)

f(n) = Ω(g(n))

     

3. 세타 표기법   Theta -  Θ(n)  : 상하한 표기(평균 표기) (평균의 경우, average case)

정의
모든 n≥n₀에 대해서 c₁g(n) ≥ f(n) ≥ c₂g(n)이 성립하는 양의 상수 c₁,c₂,n₀이 존재하면,
f(n) =Θ(g(n))

 

즉, Θ(n) =  O(n)∩Ω(n)
빅 오와 오메가 표기법의 교집합이다 ( `대략`)

f(n) =Θ(g(n))

 

4. 리틀 오 표기법  Little-o - o(n)  

정의

o(n)는 O(n) 이면서는 Θ(n) 가 아닌 조건을 만족한다 

 

정리 

빅오 (O)는 복잡도의 상한 범위를 나타낸다.
오메가 (Ω)는 복잡도의 하한 범위를 나타낸다.
세타 (Θ)는 복잡도의 평균 범위를 나타낸다.
리틀오 (o)는 복잡도의 평균 범위를 제외한 상한 범위를 나타낸다.

 

이해를 위한 그림

주로 알고리즘의 수행 시간은 빅오표기법을 사용하며, 정확히 표기하기 위하면 세타표기를 사용하기도 한다.

자주 사용되는 빅오 표기법의 이름을 더 안내하고 마무리 하겠습니다:)

• O(1)  상수 시간
• O(log n) 로그 시간
• O(n) 선형 시간
• O(nlog n ) 로그선형 시간
• O(n²) 이차 시간
• O(n³) 삼차 시간
• O(2^n) 지수 시간