2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개

1. 알고리즘의 설계

1) 최댓값 찾기

1-1) 값들을 하나씩 모두 비교해 가면서 최댓값을 찾는 방법
1-2) 토너먼트 방식
    둘씩 비교해서 큰값을 찾아가는 방법
더 효율적인것을 결정해야한다.

(n-1)번 1-1과 1-2 의 효율성은 7번으로 같다.

2) 뒤섞인 카드에서 원하는 카드 찾기

2-1) 순차탐색(Sequential Search) 순차적으로 전부 다 뒤집는다

1
2
3
4
5
6
7
8
SequentialSearch(A[], n, x)
// 배열 A[0..n-1]에서 x를 찾는 알고리즘
{
    for(i = 0; i < n; i ++){
        if(x == A[i]) return i;
    }
    return -1;
}
cs

모든 배열의 원소를 전부 다 비교


2-2) 카드가 오름차순으로 나열되어 있다면 이진탐색(binary search)

1
2
3
4
5
6
7
8
BinarySearch(A[], Left, Right, x)
{
    if(Left>Right) return -1;
    Mid = (left + right) / 2;
    if(x == A[mid]) return Mid;
    else if (x<A[mid]) BinarySearch(A, Left, Mid-1, x)
    else BinarySEarch(A,Mid+1,Right,x);
}
cs

데이터가 뒤죽박죽일때는 순차탐색, 정렬되어있다면 이진탐색이 더 좋다.

> 주어진 문제, 속성, 조건 등의 매우 다양
 => 일반적이고 범용의 기법은 미존재

> 대표적인 설계 기법
- 분할정복 divide and conquer 방법
- 동적 프로그래밍 dynamic programming 방법
- 욕심쟁이 greedy 방법

2. 알고리즘의 분석

1) 정확성 분석 (다루지않음 이미 정확하다고 증명이 된 알고리즘만 학습한다.)

  • 유효한 입력, 유한 시간 → 정확한 결과 생성하는가?
    다양한 수학적 기법을 사용해서 이론적으로 증명이 필요하다.

2) 효율성 분석 (보통의 알고리즘 분석은 효율성 분석을 말한다.)

  • 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
  • 메모리 양 > 공간 복잡도 (space complexity)
    정적 공간 + 동적 공간
    (상대적으로 계산하기 쉬움)
  • 수행시간 > 시간 복잡도 (time complexity)
    (보통의 효율성 분석은 시간복잡도를 분석하는것을 말한다.)
    시간이 덜 걸리는것이 효율성이 높다.

    알고리즘을 프로그램으로 구현해서 이를 컴퓨터에서 실행시켜 실제 수행시간을 측정
  • 이런 방법은 일반적이지 못하다!
    컴퓨터 속도, 사용한 프로그래밍 언어, 프로그램 작성방법, 컴파일러의 효율성 등에 종속적이기 때문!


    > 알고리즘이 수행하는 기본적인 연산의 횟수의 합
  • 시간 복잡도에 영향을 미치는 요인?
    - 입력으로 제공되는 데이터 크기 ("입력 크기")
    - 입력 데이터의 상태

3) 시간 복잡도

  • 입력크기 n 이 증가하면 수행 시간도 증가
    > 단순히 단위 연산의 개수가 아닌 입력 크기의 함수로 표현한다.
  • 입력 데이터의 상태(ex:정렬 비정렬)에 종속적
    - 평균 수행시간
    - 최선 수행시간 (데이터가 가장 이상적인 상태로 제공되었을 경우)
    - 최악 수행시간 (가장 데이터가 좋지않은 상태로 제공되었을 경우)
    평균수행시간이 가장 좋지만 평균수행시간을 계산이 쉽지않다. 그러므로 최악의 수행시간을 가지고 시간복잡도를 측정한다. 최악의 수행시간을 기준으로 같거나 적게 걸린다가 되므로 기준은 최악의 수행시간을 기준으로 가진다.
1
2
3
4
5
6
7
8
9
10
11
SumAverage(A[], n)
//A[0.. n-1], n : 입력 배열과 데이터 개수
    sum = 0;
    i = 0;
    while(i<n){
        sum = sum + A[i];
        i = i + 1;
    }
    average = sum / n;
    print sum, average;
}
cs

 

시간복잡도와 점근성능 빅오 표기법으로 까지 도출 할 수 있어야 한다.

 

3. 점근 성능

정의: 입력크기 n이 무한대로 커짐에 따라 결정되는 성능

데이터의 개수가 증가한다. 15개를 기준으로 효율성의 크기가 달라진다.

수행시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현
(최고차항만이 가장 큰 영향력을 행사하기 때문이다.)
수행시간의 어림값, 수행 시간의 증가 추세 파악이 용이 > 알고리즘의 우열을 표현

1) 점근성능의 표기법

1-1) 정의 'Big-oh' 점근적 상한 (최악의 수행시간)

어떤 양의 상수 c와 n0이 존재하여 모든 n≥n0에 대하여 f(n)≤cㆍg(n)이면 f(n) = O(g(n))이다.

1-2) 'Big-omega' 점근적 하한 (최선의 수행시간)

어떤 양의 상수 c와 n0이 존재하여 모든 n≥n0에 대하여 f(n)≥cㆍg(n)이면 f(n)=Ω(g(n)) 이다.

1-3) 'Big-theta' 점근적 상하한 (알고리즘의 수행시간을 좀 더 엄밀하게 나타낼 수 있다)

어떤 양의 상수 c1, c2와 n0이 존재하여 모든 n≥n0에 대하여 c1ㆍg(n)≤f(n)≤c2ㆍg(n) 이면 f(n) = Θ(g(n)) 이다.

(점근적 상하한)

 

2) 주요 O-표기 간의 연산 시간의 크기 관계


◀◀◀효율적                                                                                                                    비효율적▶▶▶
상수시간: 데이터의 개수와 상관없이 소요시간은 일정하다.

 

3) 효율적인 알고리즘의 중요성

 

4) 알고리즘의 시간 복잡도 구하기

알고리즘에 나타난 루프의 반복횟수를 조사하여 시간 복잡도로 취함
g(n)은 최고 차수에 의존

 

4. 순환 알고리즘의 성능

1) 순환 recursion, 재귀
알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태

BinarySearch() 를 계산하면 T(n) = T(n/2) + O(1), T(1) = c1

이진탐색의 수행시간은 O(log n) 이다.

일일이 점화식으로 계산하기엔 여간 복잡한게 아니다.

모두 다 기억하긴 어렵지만 2,3,6번은 기억해야한다.

한가지만 기억해도 본전 뽑는다 최! 고! 차! 항! 만 기억하자!