Algorithm 1 - analysis(1)

알고리즘(Algorithm)이란?

어떤 문제를 풀기 위한 유한한 절차와 방법을 의미합니다

문제란?

• 여기서 문제는 보통 '수학적으로 엄밀히' 정의된 문제로 한정합니다
• 조금 더 좁은 의미로는 input이 주어졌을 때, '수학적으로 엄밀히' 정의될 수 있는 ouput을 도출하는 절차와 방법을 의미합니다
• 같은 문제에 대해 여러가지 알고리즘이 존재할 수 있습니다

절차와 방법?
- 계산된 문제를 풀기 위해 -> 숫자와 사칙연산을 이용합니다
- 컴퓨터로 계산 문제를 풀기 위해 -> instruction set을 이용합니다

알고리즘의 이론적 분석 vs 실험적 분석

알고리즘의 성능(수행 시간)을 분석하는 방법

실험적 분석

• 주어진 알고리즘 소스코드를 구현한 다음 실제 환경에서 동작시켜 실제 실행 시간을 측정하는 방식입니다

문제점
- 알고리즘을 실제 구현하기 까지 시간과 노력이 소모된다는 단점이 있습니다
- 두 알고리즘의 성능을 비교할 때, 다양한 외부 요인들로 인해 정확한 비교가 어렵다는 단점이 있습니다

이론적 분석

• 알고리즘 수행 시간(= 성능)을 실제 구현을 통해서가 아닌, 이론적으로 기술하는 방법입니다
• 시간은 보통 input에 관한 함수로 표현됩니다
• 함숫값은 해당 input에 대해 알고리즘을 수행하는 데에 필요한 기본 연산의 총 횟수를 나타냅니다
• 사용하는 하드웨어 및 소프트웨어와 무관하게 알고리즘의 성능을 표현할 수 있습니다
• 이론적 분석을 통해 구한 알고리즘 수행 시간을 시간 복잡도(Time Complexity)라고 합니다

이론적 분석에서 고려하는 기본 연산들

1. 변수에 숫자를 대입
2. 함수 call, 함수의 결과를 return
3. 두 작은 정수 사이의 사칙연산
4. Array의 Get, Set
5. 기타 컴퓨터 하드웨어에서 정의된 단일 명령어

- 한 번의 기본 연산을 수행하는 데에 걸리는 시간은 외부 요인에 따라 다를 수 있습니다
	따라서 일반적으로 정확한 시간은 알 수 없습니다
- 하지만 각각의 단일 연산들은 input에 무관합니다
- 이 경우 이론적으로 이 연산들은 constant time이 소모된다고 봅니다

• 이론적 분석에서는 걸리는 시간을 표현한 함수 자체보다 input size에 따라 함숫값이 얼마나 빨리 증가하는가에 더 관심을 가집니다
• 앞선 constant time 연산들은 input size와 무관하며 함수가 증가하는 속도와도 거의 무관하다고 볼 수 있습니다

Ex) 컴퓨터 1보다 모든 기본 연산들이 10배 빠른 컴퓨터 2가 있다고 했을 때

Time Complexity	컴퓨터 1이 n개의 자료를 처리하는 데에 k 시간이 걸릴 때, 컴퓨터 2가 k 시간동안 처리할 수 있는 자료 수
$n$	$10n$
$n^2$	$2n$
$n^3$	$n + 3$

• 실제 성능에서도 복잡한 알고리즘일수록 기본 연산들의 속도차이는 거의 무의미합니다

Big-Oh Notation

Big-Oh Notation의 정의

$f(n)$과 $g(n)$을 자연수에서 실수로의 함수라고 하자.
이 때 만약 모든 $n > n_0$에 대하여

$f(n) <= c*g(n)$

을 만족하는 어떤 실수 constant $c > 0$와 자연수 $n_0 >0$이 존재하면

$f(n) = O(g(n))$
※ $f(n)$ is big-oh of (order) $g(n)$)

수학적 기호를 사용한 정의

∃ $c$, $n_0 > 0$ such that ∀$n > n_0, f(n) <= c*g(n)$

Big-Oh Notation 예시

Big-Oh notation은 반드시 가장 간략한 형태 (모든 coefficient가 1인 함수들 중 가능한 가장 증가율이 작은 함수)로 표현해야합니다
Ex1) $f(n) = 100 → O(1)$
Ex2) $f(n) = 3n^2 + 100n + 1000 → O(n^2)$

Big-Oh Notation으로 어떤 함수를 표현하는 데에 있어서 몇 가지의 규칙

1. 함수의 각 term의 coefficient는 생략 가능
2. a > b인 경우 $$n^a$$와 $$n^b$$ term이 같이 있으면 $$n^a$$ term만 남길 수 있음
3. 어떠한 exponential term도 polynomial term을 dominate함
(※ 여기서 exponential function의 base는 그대로 두기)
4. 어떠한 polynomial term도 logarithm term을 dominate함