관계기반 알고리즘의 설계

알고리즘 설계법은 크게 두 가지가 있다.

1. 관계기반 설계

각 값들 사이의 관계를 이용하여 해를 구하는 방법

함수로 표현할 수 있어야 하며, 점화식같은 형태를 이용하여 표현 할 수 있어야 한다.

2. 탐색기반 설계

컴퓨터의 빠른 연산으로, 모든 집탑을 탐색하는 방법.

크기에 비래하여 시간이 길어질 수도 있다.

때문에 배제를 한다.

ex) 1 ~ n 까지의 합

1)

f(1) = 1;

f(n) = f(n-1)+n; (n>=2)

[출처] 알고리즘 심화 - 관계기반 알고리즘의 설계|작성자 bestmaker

int f(int n)
{
    if (n == 1)
        return 1;
    else
        return f(n - 1) + n;
}

위와 같이 표현할 수 있겠다.

2)

f(k) 를 n/2 로 가정

f(1) = 1

f(5) = 1+ 2+ 3+ 4+ 5

f(11) = f(5) + (5+1) + (5+2) .... (5+6)

=2f(5)+5*6+6 = 2f(5)+6*6

>> f(n) = 2*f(n/2) + ((n+1)/2)*((n+1)/2) 

n+1 인 이유는 짝수도 적용하기 위함이다.

1의 방법은 순회하기 때문에 O(n) 인데 아래는 O(log2n) 이다.

즉 입력하는 n의 값이 클수록 2번의 방법이 효율적이란 뜻이 되겠다.