[자료구조] 12 시간복잡도 (Time Complexity)

✔️시간 복잡도 (Time Complexity)

 

프로그램이 수행을 완료하는데 걸리는 시간 

👉 컴파일 시간 (Compile Time)

👉 실행 시간 (Execution Time)

컴파일은 완료되고 나면 더 이상 수행이 되지 않으므로 시간 복잡도 평가에서 더 중요한건 ❗️실행 시간이다

 

 

 

✔️시간 복잡도 계산

물리적인 프로그램 실행 시간을 측정하는 것도 가능 but 측정하는 하드웨어 환경에 따라 결과가 달라질 수 있음 

=> 실제 수행 시간보다 실행해야 할 명령문의 수를 세어 시간 복잡도를 계산하는 방법 => 객관적 

 

 

❓명령문의 수를 측정하는 방법

1. 카운터 변수 (Counter variable) 를 프로그램 내에 포함시켜 측정

2. 실행 명령문 표 (Execution step count table)을 사용하여 측정 

 

👉 실행 명령문 표란?

함수의 헤더나 블락의 시작 또는 끝은 문장으로 간주하지 않는다

int factorial (int n){	명령문 수	빈도 수
if (n>0)	1	n+1
return n * factorial(n-1);	1	n
return 1;	1	1
}

if(n>0) true인 경우가 n번, false인 경우 1번 => n+1 번

그 다음 return 문은 if 가 true 인 n번이 수행된다

마지막 return 문은 if 가 false 인 1번 수행

 

👉 총 실행 명령문 수는 n+1 + n + 1 = 2n + 2

 

 

 

✔️ 점근적 표기법 (Asymptotic Notation)

입력의 수 n이 매우 커질 때 알고리즘의 복잡도(실행 명령문 수) 가 증가하는 패턴을 근사적으로 표현하는 것 

상한선, 하한선, 상한-하한선의 존재 유무에 따라 다음 기호를 사용하여 근사적 복잡도를 표현해낼 수 있다

 

O (빅 오) 👉 상한선 (upper bound)

Ω (오메가) 👉 하한선 (lower bound)

Θ (세타) 👉 상한-하한선 (upper and lower bound) 

 

 

📌 O (빅 오) Notation (표기법)

n0 이상인 모든 n에 대해서 f(n) <= c*g(n)을 만족하는 양의 상수 c와 n0가 존재한다면, 시간 복잡도 함수 f(n) = O(g(n))이라고 표기할 수 있다. 그리고 이 반대의 경우도 성립한다.

 

👉 시간 복잡도 함수 f(n) = O(g(n))이라 표기할 수 있다? => 이 알고리즘의 수행시간의 상한선이 c*g(n)을 넘지 않는다.

 

시간 복잡도 비교

연습해보면 ,

2n + 3 = O(n) => 모든 n>= 3에 대해서 2n+3 <= 3n

n^2 + 2n + 3 = O(n^2) => 모든 n에 대해서 성립한다 

 

 

📌 Ω (빅 오메가) Notation (표기법)

n0 이상인 모든 n에 대해서 f(n) >= c*g(n)을 만족하는 양의 상수 c와 n0가 존재한다면, 시간 복잡도 함수 f(n) = Ω(g(n))이라고 표기할 수 있다. 그리고 이 반대의 경우도 성립한다.

 

👉 시간 복잡도 함수 f(n) = Ω(g(n))이라 표기할 수 있다? => 이 알고리즘의 수행시간이 무조건 하한선인 c*g(n)보다 많이 걸린다. 

 

빅 오메가 표기법

📌 Θ (빅 세타) Notation (표기법)

n0 이상인 모든 n에 대해서 c1*g(n) <= f(n) <= c2*g(n) 을 만족하는 양의 상수 c1, c2와 n0가 존재한다면, 시간 복잡도 함수 f(n) = Θ(g(n))이라고 표기할 수 있다. 그리고 이 반대의 경우도 성립한다.

 

👉 n0이상 모든 n에 대해서 f(n)의 수행시간은 하한선 (c1 * g(n)) 과 상한선 (c2 * g(n)) 사이에 존재한다.

 

빅 세타 표기법

 

 

 

✔️시간 복잡도 함수의 종류

점근적 표기	이름	n이 충분히 클 때 수행 속도
O(1)	상수형(constant)	1 (가장 빠르다)
O(n)	1차(linear)	2
O(n^2)	2차(quadratic)	3
O(n^3)	3차(cubic)	4
O(2^n)	지수형(exponential)	5 (가장 느리다)

* 상수형(constant) => 입력의 수가 몇개인지 상관없이 항상 일정한 갯수의 명령문 처리 

 

시간 복잡도 함수의 종류

수행 속도는 명령문의 수에 반비례한다 

👉 O(log2N) >= O(n) >= O(nlog2N) >= O(n^2) >= O(2^n)