블로그 이미지
포도알77
IT 방랑기

calendar

      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  

Notice

2019.04.14 20:51 컴퓨터 알고리즘

시간 복잡도 계산, Master's theorem / 마스터 정리

1. 시간 복잡도


시간 복잡도란? 특정한 프로그램의 실제 동작 시간이 아닌, 입력 데이터의 크기 n에 대하여 기본적 연산의 횟수를 측정하는 것을 의미한다.   시간 복잡도를 표현하는 방법은 총 3가지가 있다.

  1. 최선
  2. 평균
  3. 최악

간단한 정리는 아래의 포스팅을 읽어보자. [알고리즘] 시간 복잡도, 점근적 분석법 그리고 표기법  

2. 시간 복잡도 계산


시간 복잡도 함수 `T(n)`은 일반적으로 재귀 형태의 수식으로 주어지는데, `n=1`까지 모든 항을 구해서 그 합을 구하면 그 값이 시간복잡도가 된다.   예를 들어 가장 간단한 시간 복잡도 함수를 보면,

`T(n) = T(n-1) + n`

 이 `T(n)` 함수는 1회 실행에 n번의 기본 연산을 수행하며, 다음에는 n-1개의 데이터에 대해서 재귀적으로 수행한다는 의미이다.

 이 함수를 풀어써보면,

`T(n) = 1 + 2 + ..... + n-1 + n = sum(1, n)`

 따라서 `sum(1,n)`은 등차수열의 합 공식으로 `n*(n+1)/2`임을 알 수 있고, 여기서 `T(n)= O(n^2)`을 알 수 있다.

3. 마스터 정리


마스터 정리는 특정한 시간 복잡도 함수에 대하여 빠르게 계산할 수 있는 수식이다. 따라서 어느 형태의 시간 복잡도 함수에 대해서는 적용할 수 없는 경우도 있다.

 

 위의 수식은 마스터 정리를 적용할 수 있는 형태다. 총 3가지 경우에 따라서 계산하는 방법이 다르다. 이 케이스를 나누는 방식은 a, b의 값을 바탕으로 계산한다.  

 

1번 경우

 

   위와 같이 계산할 수 있다.

  예를 들어 `T(n) = 4*T(n/2) + n` 이라면, `a = 4`, `b = 2` 이고 `log_b a = 2`이다. 이때 `f(n)`의 최고 차항이 1이므로 이 함수의 시간 복잡도는 `theta(n^2)`가 된다.

 

2번 경우

 

 예를 들어 `T(n) = 2*T(n/2) + n` 이라면, `a = 2`, `b= 2`이고 `c = 1`이다. 따라서 시간 복잡도는 `theta(n log n)`이다.

 

3번 경우

   

예를 들어 `T(n) = 2*T(n/3) + n` 이라면, `log_b a` 는 `log_3 2` 이면서, `c=1`이다. 따라서 `c > log_b a`를 만족한다. 또한 `2*(n/3) <= k(n)`의 경우 `2/3 <= k < 1`을 만족하므로 시간 복잡도는 `theta(n)`가 된다.

 

4. 마스터 정리를 적용할 수 없는 케이스


사실 저 형태의 시간복잡도가 아닌 함수는 빠르게 해결 할 수 없다. 예를 들어 `T(n) = T(n/2) + T(n/4) + n` 인 경우가 그렇다. 이 경우는 트리 형태로 그려가면서 풀면 공비가 3/4인 등비수열의 합으로 나타낼 수 있다. 또한 멱급수나, 미적분을 해야하는 경우도 있으니, 사실 많이 풀어보는게 답이다.

posted by 궁금한 포도알77
2019.04.14 19:47 컴퓨터 알고리즘

1.  시간 복잡도 시간 복잡도 (Time complexity)는 컴퓨터 공학에서 사용되는 알고리즘을 입력의 크기에 관계해서 나타내는 방법이다.  

 왜 절대 시간을 쓰지 않을까? 절대시간은 사실 컴퓨터 환경 의존성이 심하다. 예를 들어, A 알고리즘은 B 컴퓨터에서 1초동안 100개의 입력을 처리할 수 있지만, C 컴퓨터에서는 10개만 해결할 수 있다면, 이 알고리즘에 대한 절대적 평가가 힘들 수 있다.

 따라서 절대 시간이 아닌, 입력의 크기 n에 따라서 알고리즘 동작까지 필요한 시간을 n에 대한 수식으로 나타내는 것이다.

 

  2. Basic Operation 시간 복잡도를 나타낼 때, 측정하는 단위이다. "기본연산"이라고도 하며, 입력의 크기에 비례해서 나타내는 경향을 보인다. 예를 들어 아래의 코드를 실행한다고 생각하자.

for (int i = 0; i < n; i++){ // basic operation i
  array[i] *= 10;  // basic operation array[i]
}

 위의 함수는 입력받은 n개의 정수형 데이터에 10을 곱하는 동작을 한다. 여기서 변수 i와 array는 입력 크기 n에 비례하여, 곱셈과 덧셈이라는 basic operation을 수행하게 된다.

 Basic Operation은 사실 관점에 따라서 기준이 바뀔 수 있다. 예를 들어 산술 연산( +, -, *, /, %)만 포함하는 경우가 있으며, 비트 연산 그리고 대입 연산까지 포함하는 경우도 있다.

 

  3. 시간 복잡도 표기법 위와 같이 시간복잡도를 표기하는 방법을 정의하기 앞서 알고리즘이 가지는 불확실성에 대해서 고려해야 한다.

 만약 가장 작은 숫자를 찾는 문제를 생각해보자. n개의 입력에서 가장 작은 숫자가 어디 포함될 지 컴퓨터가 예상할 수 있을까?

inputs1 = { 1, 5, 2, 3, 7 } // best case
inputs2 = { 2, 3, 1, 3, 9 } // average case
inputs3 = { 9, 8, 7, 4, 1 } // worst case

이 처럼 우리는 세가지 경우로 나누어 생각해야 한다.

  1. 최선의 경우 (대부분 첫 시행에 찾아진다.)
  2. 평균의 경우 (최선과 최악의 산술 평균 값이다.)
  3. 최악의 경우 (대부분 맨 마지막 경우에 찾아진다.)

 만약 입력의 크기 n=100,000,000이라면, 최선의 경우에는 1번만에, 최악의 경우에는 n번만에 찾을 것이다. 따라서 이러한 조건들을 표기하기 위하여, 총 3개의 표기법을 제공한다.

  1. Omega Notation
  2. Theta Notation
  3. Big O Notation

 

4. 시간 복잡표 표기법 상세

(1) Omega Notation

오메가 표기법은 충분히 큰 n개의 입력에 대하여, 시간 복잡도 함수가 f(x)일 때,

`g(x) <= f(x)`

를 만족하는 함수를 말한다.

 예를 들어 f(x)가 3n+2 라고하자, 이 함수는 항상 g(x) = n보다 크다. 따라서 Omega(n) 이라고 표기한다.

 

(2) Theta Noation

세타 표기법은  충분히 큰 n개의 입력에 대하여, 시간 복잡도 함수가 f(x) 일 때,

`g1(x) <= f(x) <= g2(x)`

를 만족하는 함수를 말한다.

 예를 들어 f(x)가 3n+2 라고하자, 이 함수는 항상 g1(x) = n보다 크고, g2(x)=10*n보다 작다. 따라서 Theta(n) 이라고 표기한다.

 

(3) Big O Notation

빅 오 표기법은  충분히 큰 n개의 입력에 대하여, 시간 복잡도 함수가 f(x) 일 때,

`f(x) <= g(x)`

를 만족하는 함수를 말한다.

 예를 들어 f(x)가 3n+2 라고하자, 이 함수는 g(x)=10*n보다 작다. 따라서 O(n) 이라고 표기한다.

 사실 이 포스트에 내용은 굉장히 축약되어 있는 편이다. 따라서 어떠하다 정도만 이해하고, 위키피디아를 참고하여 보충하길 바란다.

posted by 궁금한 포도알77
prev 1 next