Foundation of Algorithm - CHAPTER 1

 

 

CHAPTER 1 - Algorithms : Efficiency, Analysis, and Order

---

1.1 알고리즘 (Algorithm)

- 리스트(list)란 어떤 원소를 특정 순서로 나열해 놓은 것이다.
(ex) S = [10, 7, 11, 5, 13 ,8]

- 순차검색 ( Time Complexitiy : O(n))
: 반복문을 통해 배열의 start index부터 end index까지 한번씩 검색하는 알고리즘.

void seqsearch(int n, const keytype S[]. keytype x, index& location)
{
  location = 1;
  while(location <= n && S[location] != x)
    location++;

  if(location > n)
    location = 0;
}

 

- 교환 정렬(Exchange Sort)
: 반복문을 통해 배열의 start index부터 end index까지 한번씩 검색하는 알고리즘.

void exchange(int n, keytype S[])
{
  index i, j;
  for (i = 1; i <= n-1; i++)
    for(j = i+1; j <= n; j++)
        if(S[j] < S[i])
          exchange S[i] and S[j];
}

---

 

1.2 효율적인 알고리즘 개발의 중요성

* 순차검색 대 이분검색

- 순차 검색(Sequential Search)보다 이분 검색(Binary Search)를 통해 효율적으로 Search 할 수 있다.

- 이분 검색(Binary Search) : 배열이 정렬되어 있다는 가정이 필요.
1. 찾고 싶은 수를 x라고 할 때, 배열의 정중앙에 위치한 원소 y와 비교한다.
2. 만약 x를 찾았다면, 검색을 종료한다.
3. 만약 x를 찾지 못했을 때 x가 y보다 크면 배열의 앞부분을, x가 y보다 작다면 배열의 뒷부분을 이분 검색한다.

void binsearch (int n, const keytype S[], keytype x, index& location)
{
  index low, high, mid;
  
  low = 1; high = n;
  location = 0;

  while(low <= high && location == 0) {
    mid = (low + high) / 2;

    if(x == S[mid])
     location = mid;
    else if(x < S[mid])
     high = mid - 1;
    else
     low = mid + 1;
  }
}

- 크기가 n인 배열에 대해 순차 검색에 의한 비교 횟수는 n 이고, 이분 검색에 의한 비교 횟수는 log(n) + 1 이다.

 

* 피보나치 수열

▶ 재귀함수를 사용하는 방법 (Divide and Conquer 기법)
- 피보나치 수열의 n번째 수는 재귀(Recursively)로 정의한다.

$$ f_{0} = 0 $$

$$ f_{1} = 1 $$

$$ f_{n} = f_{n-1} + f_{n-2} (if \; n \geq 2) $$

int fib (int n)
{
  if (n <= 1)
   return n;
  else
   return fib(n-1) + fib(n-2);
}

 

5번째 피보나치 항을 표현하는 Recursion Tree

- T(n)을 n에 대한 Recursion Tree의 항의 개수라고 할 때,

$$ T(n) > 2 \times T(n-2)   
\\
\\
> 2 \times 2 \times T(n-4)
\\
\\
> 2 \times 2 \times 2 \times T(n-6)
\\
\\
> 2 \times 2 \times 2 \times ... \times T(0)  $$

 

- 따라서, 재귀함수를 사용하여 피보나치 함수를 구현하면 구하는 항의 갯수 T(n)은 아래 관계를 만족한다.

$$ T(n) > 2^{\frac{2}{n}} $$

 

▶ 배열과 반복문을 사용하는 방법 (Dynamic Programming 기법)

- 이에 재귀함수를 사용하는 대신, 배열과 반복문을 사용하여 좀 더 효율적이게 피보나치 수를 구하는 알고리즘을 작성할 수 있다.

int fib2 (int n)
{
  index i;
  int f[0..n];

  f[0] = 0;
  if ( n > 0) {
    f[1] = 1;
    for ( i = 2; i <= n; i++)
      f[i] = f[i-1] + f[i-2];
  }

  return f[n];
}

- 이 방법은 n번째 피보나치 항을 구하기 위해서 (n+1) 개의 항을 계산한다.

 

 

---

1.3 알고리즘의 분석 (Analysis of Algorithms)

 

* 시간복잡도 분석(Complexity Analysis)

- 일반적으로 알고리즘의 실행시간은 입력의 크기가 커지면 증가하고, 총 실행시간은 ​단위 연산이 몇 번 수행되는가에 비례한다.
- 알고리즘의 시간복잡도 분석(Time Complexity Analysis)는 입력크기를 기준으로 단위 연산을 몇번 수행하는지 구하는 것이다.
- 교환정렬(Exchange Sort)의 시간복잡도는,

$$ T(n) = (n-1) + (n-2) + (n-3) + ... + 1 = \frac{n(n-1)}{2} $$

- 크기가 n이어도, 단위 연산을 수행하는 횟수가 달라질 수 있다. (ex) 순차검색
- 이에 시간복잡도를 측정할 때, 알고리즘이 실행할 단위연산의 최대 횟수를 사용하여  최악 시간복잡도(Worst-case Time Complexity)를 구하여 사용할 수 있다.
- 순차 검색(Sequential Search)의 Worst-case time Complexity W(n) = n이다.

- 알고리즘이 평균적으로 얼마나 실행하는지를 알면, 더 효율적인 경우도 존재한다.
- 이 경우에는, 평균 시간복잡도(Average-case Time Complexity)를 구하여 알고리즘을 분석하는 경우가 더 합리적일 수 있다.
- 평균 시간복잡도를 구하기 위해서는 n개의 입력에 확률을 각각 부여해야 한다.
- 순차검색(Sequential Search)에서 찾고자 하는 수 x가 배열 S에 있는 경우는,
  (x가 k번째 위치에 있을 확률 : 1/n)

$$ A\left(n\right)\ =\ \sum _{k=1}^n\left(k\times \frac{1}{n}\right)\ =\ \frac{1}{n}\times \sum _{k=1}^nk\ =\frac{1}{n}\ \times \frac{n\left(n+1\right)}{2}\ =\ \frac{n+1}{2} $$

 

- 순차검색(Sequential Search)에서 찾고자 하는 수 x가 배열 S에 없는 경우에는,
  (x가 k번째에 위치할 확률 p/n, x가 배열에 없을 확률 1-p)

$$ A\left(n\right)\ =\ \sum _{k=1}^n\left(k\ \times \frac{p}{n}\right)\ +\ n\left(1-p\right)\ =\ n\left(1-\frac{p}{2}\right)\ +\frac{p}{2} $$

- 알고리즘이 실행할 단위연산의 최소 횟수를 통해 최선 시간복잡도(Best case Time Complexity)를 구할 수 있다
- 순차 검색(Sequential Search)의 Best-Case Time Complexity B(n) = 1이다.

---

 

1.4 차수 (Order)

- 시간복잡도(Time Complexity)가 n, 100n과 같은 경우 linear-time Algorithm 이라고 한다.
- 시간복잡도(Time Complexity)가 (n^2), (0.01n^2)과 같은 경우 quadratic-time Algorithm이라고 한다.

 

* 차수의 직관적인 소개(An Intutive Introduction to Order)

Complexity Function의 증가율

$$ \theta \left(\lg n\right)\ <\theta \left(n\right)\ <\ \theta \left(n\lg n\right)\ <\ \theta \left(n^2\right)\ <\ \theta \left(n^3\right)\ <\ 2^n $$

 

* 차수의 정식 소개 (Rigorous Introduction to Order)

1. Big-O

- 주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 정수 N 이상의 모든 n에 대해서 다음 부등식이 성립하는
  양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

$$ g\left(n\right)\ \le \ c\ \times f\left(n\right) $$

 - Big O는 함수의 asymptotic upper bound(점근적인 상한)을 정한다.

 

2. Omega

- 주어진 복잡도 함수 f(n)에 대해서 Omega(f(n))은 N이상의 모든 n에 대해서 다음 부등식을 만족하는
양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

$$ g\left(n\right)\ \ge \ c\ \times f\left(n\right) $$

 

 - (Big-O)와 Omega와 Theta

 

---

-Reference-
Neapolitan, Richard E., 『Foundation of algorithms FIFTH EDITION』