알고리즘과 귀납적 사고

  알고리즘과 귀납적 사고 

알고리즘이란?

어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것으로 알고리즘을 설계하기 위해서는 해야 할 작업을 명확하게 명시해야 한다.

 

※ 알고리즘이 명확하다는 것은 모호하지 않고 이해하기 쉬운 것을 의미하며 자세한 것과는 다르다.

 

알고리즘은 가능하면 효율적이어야 하며 그중 작은 입력보다는 충분히 큰 입력에 대해 관심을 가져야 한다. 이렇게 큰 입력에 대한 분석을 점근적 분석(Asymptotic Analysis)라고 한다.

 

알고리즘을 분석하는 이유

어떠한 입력을 일정 시간 이내에 처리해야 할 때 적용할 수 있는 알고리즘의 시간 분석을 하면 각 알고리즘이 어느 정도의 시간이 소요되는지 파악하여 적절한 알고리즘을 적용할 수 있다.

 

※ 일반적인 상황에서 알고리즘 분석 시 소요시간이 가장 큰 관심사가 된다.

 

알고리즘의 수행 시간

입력의 크기에 대해 시간이 어떤 비율로 소요되는지 표현하는 것을 말한다.

이에 대한 몇 가지 예를 들면 다음과 같다.

 

Code(A[], n)
{
    sum <- 0
    for i <- 1 to n
        sum <- sum + A[i]
    return sum
}

이 코드의 경우 반복문 내부의 작업은 상수 시간만을 소요하기 때문에 전체적인 소요 시간은 반복문에 관련된 n에 비례하게 된다.

 

Code(A[], n)
{
    sum <- 0
    for i <- 1 to n
        for j <- 1 to n
            sum <- sum + A[i] * A[j]
    return sum
}

또, 위와 같이 배열의 모든 원소 쌍의 합을 구하는 알고리즘의 경우에 중첩된 반복문이 각각 n의 시간을 소요하기 때문에 n * n = n^2의 시간을 소요하게 된다.

 

대부분 이런 식으로 소요시간을 구할 수 있으나 재귀 함수의 경우 자기 호출하는 경우를 생각하지 않으면 상수 시간 호출로 생각되므로 자기 호출한 횟수가 소요 시간을 좌우하게 된다.

 

Code(n)
{
    if (n == 1) return 1
    return n * Code(n - 1)
}

위와 같은 팩토리얼 함수의 경우 단순하게 함수 자체의 소요 시간은 상수 시간이 된다. 하지만 자기 호출하는 경우를 따지면 총 수행 시간은 n에 비례하는 것을 알 수 있다.

 

재귀와 귀납적 사고

재귀를 사용하는 알고리즘이 많으며 일반적으로 재귀와 관계없다고 생각하는 선택 정렬이나 버블 정렬도 재귀적 관점에서 보면 이해하기 쉬워진다.

 

귀납적 사고는 작은 입력에 대해 옳다고 가정하고 큰 입력에 대한 처리를 진행하는 것을 말한다.

이는 수학적 귀납법의 작은 값에 대해 옳다고 가정하고 문제와의 관계를 통해 결론이 옳음을 보이는 것과 비슷하다.

 

알고리즘으로 푸는 문제

• 최단경로 알고리즘 두 지점 간의 최단경로 혹은 최단시간의 경로를 찾는 것
  • ex) 네비게이션
• 스케줄링 한정된 자원을 효율적으로 이용하는 방법
  • ex) 자판기 관리
• 검색 원하는 검색 결과를 최대한 빨리 반환하는 것
  • ex) 인터넷 검색 엔진
• 정렬 주어진 값을 정해진 순서대로 정렬하는 방법
  • ex) 고객 메일링 리스트

 

점근적 표기

알고리즘의 효율성을 분석하기 위해 매우 큰 입력을 가정하여 분석하는 데 이 분석을 점근적 분석이라 한다.

 

극한에 대한 문제가 이러한 점근적 분석의 예이다.

이것의 의미는 n이 충분히 커짐에 따라 n의 비율로 증가한다는 것이다.

 

추가적으로 n와 10n, 2n^2의 예를 들면 다음과 같다.

n	10n	2n^2
1	10	2
2	20	8
10	100	200
1,000	10,000	20,000
10,000	100,000	2,000,000
100,000	1,000,000	200,000,000
1,000,000	10,000,000	2,000,000,000,000
10,000,000	100,000,000	200,000,000,000,000
...	...	...
10^10	10^11	2*10^20
10^20	10^21	2*10^40

 

예제에서 확인할 수 있다시피 n 앞의 계수는 초기에는 큰 영향을 주지만 n이 커질수록 그 영향력이 작아지고 결국엔 무시할 수 있을만한 수준이 된다는 것을 알 수 있다.

 

※ 점근적 분석은 계수와 상수를 무시한다.

 

여러 가지 점근적 표기법

점근적 표기법에는 대표적인 빅오 표기법 외에도 여러가지 표기법이 존재한다.

• 세타(Θ) 표기법 최고차 항의 차수가 주어진 함수의 차수와 일치하는 함수들의 집합... 동등(≒)
  • { n², 3n² + 4, n² + nlogn, ... } = Θ(n²)
• 빅오(Ο) 표기법 최고차 항의 차수가 주어진 함수의 차수와 같거나 작은 함수들의 집합... 이하(≤)
  • { 2n², 3n, 2nlogn, ... } = Θ(n²)
• 오메가(Ω) 표기법 최고차 항의 차수가 주어진 함수의 차수와 같거나 큰 함수들의 집합... 이상(≥)
  • { n² + n, 3n³ + 4n, 6n⁴ + logn, ... } = Θ(n²)
• 리틀오(ο) 표기법 최고차 항의 차수가 주어진 함수의 차수보다 작은 함수들의 집합... 미만(＜)
  • { 3n, 2nlogn, ... } = Θ(n²)
• 리틀오메가(ω) 표기법 최고차 항의 차수가 주어진 함수의 차수보다 큰 함수들의 집합... 초과(＞)
  • { 3n³ + 4n, 6n⁴ + logn, ... } = Θ(n²)

 

※ 각 표기법은 집합으로 정의되며 동등 기호(=)는 집합의 포함 기호(∈)를 대신해 사용하는 것이므로 반드시 표기법이 우측에 위치해야 한다.

 

점화식의 점근적 분석 방법

대표적인 방법으로 반복 대치, 추정후 증명, 마스터 정리가 존재한다.

 

- 반복 대치

: 어떤 함수의 입력이 n일 때 소요 시간을 T(n)이라 할 경우 T(n)을 T(n - 1)로 대치하고 T(n - 1)을 T(n - 2)로 대치하는 것을 반복하여 T(1)까지 대치하는 분석 방법이다.

 

---

어떤 함수의 입력이 n일 때 소요 시간 T(n)은 다음과 같이 나타낼 수 있다.

 

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

 

이때 c는 자기 호출을 제외한 나머지를 수행하는 시간을 나타낸다. 

---

 

병합 정렬 알고리즘의 반복 대치를 통한 분석은 다음과 같이 진행할 수 있다.

 

MergeSort

MergeSort(A[], p, r)
{
	if (p < r) then {
    	q ← |_ q + r / 2 _|
        MergeSort(A[], p, q)
        MergeSort(A[], q + 1, r)
        Merge(A, p, q, r)
    }
}

 

입력이 n 일 때 소요 시간을 T(n)이라고 하면 다음과 같이 나타낼 수 있다.

A: 병합 정렬을 반으로 나눠 실행하기 때문에 발생

B: 병합 정렬 후 통합 작업 실행으로 발생

 

이를 전개하면 다음과 같다.

 

※ n = 2^k로 가정해도 일반성을 잃지 않으므로 이를 k에 대한 식으로 쓰면 k = logn이 된다.

 

---

n = 2^k로 가정해도 되는 이유는 다음과 같다.

 

어떤 n이라도 n과 2n 사이에는 2의 멱수가 하나 존재한다.

이때 임의의 상수 r에 대해 T(n) = O(n^r)이면 T(2n) = O((2n)^r) = O(2^rn^r) = O(n^r)이므로 T(2n) = T(n)이 된다.

 

이를 위의 사실에 대해 적용하면

T(n) ≤ T(2^k) ≤ T(2n)으로 볼 수 있고 이때 T(n) = T(2n)이므로 T(n) = T(2^k) = T(2n)의 관계가 성립한다.

 

그러므로 n 이후로 처음 만나는 2의 멱수도 항상 n에 대한 함수와 같은 점근적 복잡도를 지니므로 n = 2^k로 가정해도 문제가 없게 된다.

---

 

- 추정후 증명

추정후 증명은 식의 모양을 보고 점근적 복잡도를 추정한 뒤 그것이 옳음을 증명하는 방법으로 추정을 의미 있게 하는 것이 중요하다. 이때, 적절한 추정을 위해서는 여러 식을 분석하고 결과를 얻는 과정을 반복해 직관을 얻어야 한다.

 

※ 추정을 너무 크게 한다면 의미가 없는 결과를 얻게 되고 추정을 너무 작게 한다면 증명이 불가능하다.

 

- 마스터 정리

마스터 정리는 T(n) = aT(n/b) + f(n)과 같은 모양을 가진 재귀식에 대해 결과를 바로 알 수 있는 것으로 상세한 내용은 다음과 같다.

---

1. 어떤 양의 상수 ε에 대하여 f(n)/h(n) = Ο(1/n^ε)이면, T(n)=Θ(h(n))이다.
2. 어떤 양의 상수 ε에 대하여 f(n)/(h(n) = Ω(n^ε)이고, 어떤 상수 c(< 1)와 충분히 큰 모든 n에 대해 af(n/b) ≤ c(fn)이면 T(n) = Θ(f(n))이다.
3. f(n)/h(n) = Θ(1)이면 T(n) = Θ(h(n) logn)이다.

---

 

- 마스터 정리의 근사 버전

a ≥ 1, b ＞ 1에 대해 T(n) = aT(n/b) + f(n)인 점화식에서 n^log_ba = h(n)이라 할 때 T(n)의 개략적인 점근적 복잡도 다음과 같다.

---

1. lim_n->∞ f(n)/h(n) = 0 이면 T(n) = Θ(h(n))이다.
2. lim_n->∞ f(n)/h(n) = ∞이고, 충분히 큰 모든 n에 대해 af(n/b) ＜ f(n)이면 T(n) = Θ(f(n))이다.
3. f(n)/h(n) = Θ(1)이면 T(n) = Θ(h(n) logn)이다.

---

 

※ 마스터 정리와 근사 버전은 정확히 일치하는 것이 아니다.

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘