알고리즘과 효율성 분석

알고리즘이란?

문제를 해결하는 단계적인 절차를 말한다.

 

알고리즘을 설계하고 분석하는 기술을 배우는 이유는 무엇일까?

새로운 문제에 직면했을 때 그 문제를 해결하기 위한 방법들을 익혀두기 위함이다.

여러 가능한 방법들이 있을 때 알고리즘 분석을 통해 어떤 방법을 선택할 지 결정할 수 있도록 수치화 하는 능력을 길러야 한다.

-> 문제 해결력 제고

 

 

알고리즘 분석 요소

알고리즘을 수행했을 때 소요되는 시간

알고리즘을 수행할 때 차지하는 메모리 공간

 

 

알고리즘 분석

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

input size에 따라서 basic operation이 몇번 수행되는 지 결정하는 절차를 말한다.

CPU에서의 실제작동 시간, 명령문의 개수, 프로그래밍 언어, 프로그래머, 포인터의 setting과는 독립적인 측정법이다.

 

일반적으로 알고리즘의 실행 시간은 입력 크기에 따라 증가하고, 총 실행시간은 basic operation이 몇번 수행되는가에 거의 비례하므로, basic operation이 수행되는 횟수를 입력의 크기에 대한 함수로 구한다.

 

Basic operation

- Comparison, assignment, multiplication

Control structure를 이루는 명령문은 보통 단위연산으로 취급하지 않음.

 

input size

- 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, tree에서 node와 edge의 수.

- basic operation에 대하여 가장 효율적인 구현이 이뤄진다고 가정함.

 

 

알고리즘 분석 방법

T(n) : Every-case time complexity

input size에만 의존하여 분석.

input values와는 무관하게 결과 값은 항상 일정하다.

 

W(n) : Worst-case time complexity

input size와 input values에 따라 분석.

Basic operation이 수행되는 횟수가 최대인 경우를 선택.

 

A(n) : Average-case time complexity

input size와 input values에 따라 분석.

basic operation이 수행되는 기대치(평균)

각 input에 대해서 probability assignment 가능하고 일반적으로 최악의 경우보다 계산이 복잡하다.

 

B(n) : Best-case time complexity

input size와 input values에 따라 분석.

basic operation이 수행되는 횟수가 최소인 경우를 선택.

 

 

예시 1. Add Array Items

problem : 크기가 n인 배열S의 모든 수를 더하라.

input : 양의 정수 n, 배열S[1..n]

Output : 배열S에 있는 모든 수의 합.

int sum(int n, const int S[])
{
    int i, result;
    result = 0;
    for(i=0;i<n;i++)
    	result += S[i];
    return result;
}

- Ever-case time complexity analysis

Basic operation : addition

배열 내용에 상관없이 for-loop가 n번 반복한다.

각 루프마다 덧셈이 1회 수행된다.

=> n에 대해서 덧셈이 수행되는 총 횟수는 T(n) = n 이다.

 

 

 

 

차수를 고려한 분석 방법

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

\( g(n) \le c \times f(n) \)

점근적 증가율이 \(f(n)\) 을 넘지 않는 모든 함수들의 집합.

 

\( O(f(n)) \) 최고차항의 차수가 \(f(n)\) 과 일치하거나 더 작은 함수들의 집합.