알고리즘 - 2 알고리즘의 설계와 분석의 기초

 

 

알고리즘 수행 시간 분석

1. 알고리즘 수행 시간

2. 알고리즘 수행 시간 분석 방법

 

 

알고리즘의 수행 시간

1. 알고리즘의 효율성을 분석하는 방법은 다양하지만 많은 경우에 알고리즘의 수행 시간을 이용하여 효율성 분석

- 실제로 구현하는 것이 필요함

- 동일한 하드웨어를 사용해야 함

 

2. 입력 크기에 대해 시간이 어떤 비율로 소요되는지 중요함

- 숫자의 정렬, 탐색의 입력 크기 : 숫자의 개수

- 지하철 최단 거리 탐색의 입력 크기 : 관련 노선도의 지하철 역의 개수

 

 

알고리즘 수행 시간 분석 방법

1. 수행시간이 상수인 예제

2. 수행 시간이 입력 n에 비례하는 예제

3. 수행 시간이 입력 n^2에 비례하는 예제

4. 수행 시간이 입력 n^3에 비례하는 예제

 

 

 

1. 수행시간이 상수인 예제

example1 (A[], n)
{
   i <- floor(n/3);
   return A[i];
}

- 입력 크기인 n이 변하여도 n의 개수에 비례하여 시간은 변하지 않음

- 상수 시간 소요

 

 

2. 수행 시간이 입력 n에 비례하는 예제

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

 

- 입력 크기인 n이 변하면 수행 시간은 n의 개수에 비례하여 증가함

- 입력 n에 비례하여 수행 시간 소요

 

2. 수행 시간이 입력 n에 비례하는 예제 - 2

factorial(n)
{
   if (n=1) return 1;
   return n * factorial(n-1);
}

- 펙토리얼 예제

- 재귀 알고리즘 예제

- 함수 팩토리얼이 몇 번 수행되는지가 수행 시간을 좌우함

- 총 호출 횟수 n

 

3. 수행시간이 입력 n^2에 비례하는 예제

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

- 입력 크기 n이 변하면 수행 시간은 n^2에 비례하여 증가함.

 

 

4. 수행 시간이 입력 n^3에 비례하는 예제

example4 (A[], n)
{
   sum <- 0;
   for i <- 0 to n-1
      for j <- 0 to n-1
         tmp <- A[]에서 임의로 n/2개를 뽑았을 때 이중 최대값;
         sum <- sum + tmp;
    return sum
}

- A[]에서 임의로 n/2개를 뽑았을 때 이중 최대 값 -> n에 비례하여 증가함

- 입력 크기인 n이 변하면 수행 시간은 n^3에 비례하여 증가함 -> n^3에 비례하여 수행 시간 소요

 

 

 

재귀와 귀납적 사고

1. 재귀 함수

2. 수학적 귀납법

 

 

재귀 함수

1. 문제를 해결하는 과정에서 해결하는 문제와 크기만 다르고, 자신의 해결 방법을 동일하게 적용하여 해결할 수 있는지 파악하여 주어진 문제를 푸는 방법

-> recursion, 되부름, 자기 호출 등으로 불림

2. 많은 알고리즘에서 사용

- 대표적으로 병합 정렬, 퀵 정렬, 하노이의 탑 문제, 팩토리얼 등

- 예시

 -> factorial : N! = N x (N-1)!

 -> 수열의 점화식 : a_n = 2 * 2 a_(n-1)

 

 

수학적 귀납법

1. 어떤 성질이 모든 자연수에 대해 성립함을 증명하기 위해 사용되는 방법

- 첫 번째 자연수에 대해서 참임을 증명

- 어떤 자연수에 대해서 참이면, 다음 자연수도 참임을 증명

 

2. 재귀 호출의 정당성은 수학적 귀납법과 관련됨 즉, 자기보다 작은 문제에 대해서 이 알고리즘이 제대로 작동한다고 가정

-> 자신보다 작은 문제에 대해 결론이 참임을 가정

-> 작은 문제와 자신의 문제의 관계를 파악하고, 자신의 문제에서도 결론이 맞음을 보임

 

3. 알고리즘 설계 시 유의점

-> 무한 루프에 빠지지 않도록 주의해야함

-> 재귀적인 관계를 잘 파악해야함

 

 

점근적 표기법

1. 복잡도의 점근적 표기

2. O(빅오)표기법

3. $\Omega$(빅 오메가) 표기법

4. $\Theta$(세타)표기법

5. 효율적인 알고리즘이 필요한 이유

 

 

복잡도 점근적 표기

1. 입력의 크기가 작은 문제

- 알고리즘의 효율성이 중요하지 않음

- 비효율적인 알고리즘도 무방

2. 입력의 크기가 충분히 큰 문제

- 알고리즘의 효율성이 중요함

- 비효율적인 알고리즘은 치명적임

3. 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라고함.

 

점근적 표기

- 복잡도는 입력도 크기에 대한 함수로 표기하는데, 이 함수는 주로 여러 개의 항을가지는 다항식

- 다항식을 단순한 함수로 표현하기 위해 점근적 표기를 사용함

- 입력의 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법

표기법	내용
빅오 표기법	최악의 경우 : 어떠한 경우에도 표기된 함수만큼의 성능은 보장(점근적 상한)
빅오메가 표기법	최선의 경우 : 운이 좋다면, 알고리즘은 표기된 함수만큼의 성능을 낼 수도 있음(점근적 하한)
세타 표기법	알고리즘이 거의 정확한 성능

 

 

알고리즘의 성능차

- 대규모의 데이터를 다룰때 확연하게 드러남

- ex. 연산 회수가 n^2+n인 알고리즘과 53n인 알고리즘 비교

- 데이터의 개수가 많을 수록 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른항들은 상대적으로 무시함

 -> 이때문에 점근적 표기법에서는 최고차항만으로 알고리즘의 성능을 대략적으로 표기

 

 

 

O(빅-오) 표기법

- 점근적 상한선

- 최악의 경우 알고리즘 수행 시간을 나타냄

 -> 최악의 경우에도 성능을 보장하기 떄문에 가장 많이 사용하는 알고리즘 성능 표기법

-복잡도 f(n)과 O-표기를 그래프로 나타낸 것

- n이 증가함에 따라 O(g(n))이 점근적 상한이 됨.

- 빅오 표기법 종류 및 그래프

O 표기법	설명	해당 알고리즘
O(1)	최악의 경우에도 상수 시간 안에 종료됨	해시 테이블
O(log n)	최악의 경우에도 입력 개수 n이 배로 증가하더라도, 수행 시간의 증가가 일정한 속도 안에 종료됨 - ex : 입력데이터 10개를 처리하느데 1초걸린경우, 100개를 처리하는데 2초, 1000개를 처리하는데 3초걸리는 경우	이진 탐색
O(n)	- 최악의 경우에 입력의 개수 n만큼 수행 시간 안에 종료됨 - 입력의 개수 n이 증가하는 속도만큼 수행 시간도 일정하게 증가함	순차 탐색
O(n log n)	- log n이 상수 시간보다 증가율이 크기 때문에 n log n은 n과 n^2 사이에 존재함	병합 정렬
O(n^2)	- 최악의 경우 입력 개수 n에 대한 제곱 만큼 수행 시간 안에 종료 됨	버블 정렬, 삽입 정렬
O(n^3)	- 최악의 경우 입력 개수 n에 대한 3제곱 만큼 수행 시간안에 종료됨	행렬 곱셈
O(2^n)	- 최악의 경우 입력 개수 n에 대해서 최대 2의 n제곱 만큼 수행 시간 안에 종료됨

 

$\Omega$(빅 오메가) 표기법

- 점근적 하한선

- 최선의 경우 알고리즘 수행 시간을 나타냄 -> 거의 쓰이지 않음

- 복잡도 f(n)과 $\Omega$-표기 그래프

- n이 증가함에 따라 $\Omega$(g(n))이 점근적 하한이라는것

- 즉, g(n)이 $n_0$보다 큰 모든 n에 대해서 항상 f(n)보다 작다는 것을 보여줌



 

$\Theta$ 표기법

- 점근적 상한선과  점근적 하한선의 교집합

- 복잡도 f(n)과 $\Theta$-표기를 그래프로 나타낸 것