| # | 도전 과제 | 통과 |
|---|---|---|
| 1 | 시간 복잡도 분석 | 알고리즘 | |
| 2 | 수행시간 측정 | 시간 복잡도 |
준비중..
02 알고리즘이란?
# 알고리즘이란?
## 목차
1. 알고리즘이란?
2. 자료구조와 알고리즘의 관계
3. 알고리즘의 선택기준
4. 실험적 분석과 한계
5. 이론적 분석
+ 성장률
+ 빅오 표기법
+ 복잡도 분석 예
+ 빅오-세타-오메가 표기법
## 1. 알고리즘이란?
알고리즘이란 문제를 해결하는 방법이다. 예를 들어 오렌지 주스를 만든다고 해보자. 다양한 방법들이 존재할 것이다.
+ 오렌지를 손으로 쥐어 짠다.
+ 오렌지를 양파망에 넣고 발로 밟는다.
+ 녹즙기를 사용한다.
+ etc..
위의 예 중, 방법을 선택해보자. 그리고 그 이유를 설명해보자. 아마도, 보다 쉽고 합리적이라 생각되는 방법을 선택했을 것이다.
컴퓨터를 통한 문제 해결 또한 마찬가지다. 어떤 문제를 보다 효율적 합리적으로 풀 수록 좋은 알고리즘이다.
## 2. 자료구조와 알고리즘간의 관계
그렇다면 알고리즘은 자료구조와 어떤 관계가 있을까? 정답부터 말하면, 좋은 알고리즘을 만들기 위해 필요한 것이 자료구조이다.
'계란을 깨지지 않게 보관하기'라는 문제가 예로 들자. 이를 해결하기 위한 방법으로 계란판에 보관하는 방법을 택하자. 이때 계란판은 문제 해결을 위한 자료구조가 된다.
## 3. 알고리즘의 선택기준
하나의 문제를 두고 다양한 알고리즘이 존재할 수 있다. 우리는 이들 중 현명한 알고리즘을 선택해야 한다. 선택의 기준은 크게 두 가지로 나뉜다. 바로 **실험적 분석**과 **이론적 분석**이다.
## 4. 실험적 분석과 한계
실험적 분석은 실제 실행시간(running time)을 측정하는 방법이다.
```
long startTime = System.currentTimeMillis(); // 시작 시간
doAlgorithm();
long endTime = System.currentTimeMillis(); // 종료 시간
long elapse = endTime - startTime; // 소요 시간 = 종료 시간 - 시작 시간
```
실험적 분석방법은 알고리즘 외적 요인들로 인한 한계점이 있다. 예를 들어 컴퓨터의 성능, 구현 언어의 차이, 다른 프로세스들의 간섭 등으로 결과가 달라 질 수 있다.
+ 하드웨어의 성능에 따른 영향
+ 구현 언어에 따른 영향
+ 현재 실행 중인 다른 프로세스들에 의한 영향
## 5. 이론적 분석
이를 보완한 방법이 **이론적 분석** 방법이다. 이론적 분석은 알고리즘 내적 요인을 기반으로 분석한다. 외적 요인 모두 동일 하다 가정한다.
### 5.1 성장률(Growth Rate)
성장률이란 이론적 분석의 지표이다. 크게 7가지가 있다.
다 외우려 하지 말고, 일단 3가지만 기억 하자.
+ O(1): 상수시간 내 처리 가능
+ O(n): 선형시간 내 처리 가능
+ O(n^2): 이차시간 내 처리 가능
### 5.2 빅오 표기법
빅오 표기법 또한 이론적 분석의 핵심이다. 빅오 표기법은 최악의 경우 알고리즘의 복잡도(이론적 수행시간)를 나타낸다.
O(1)은 데이터 크기에 상관없이 일정한 복잡도를 갖는다. O(n)은 데이터 크기에 정비례한 복잡도를 의미한다. O(n^2)은 데이터 크기의 제곱에 비례한 복잡도를 나타낸다.
### 5.3 복잡도 분석 예
그렇다면 실제로 분석연습을 해보자. 아래 코드의 수행 속도는 얼마일까?
```
public static double arrayMax(double[] data) {
int n = data.length; // O(1)
double currentMax = data[0]; // O(1)
for (int i = 1; i < n; i++) { // O(n)
if (data[i] > currentMax) // O(1)
currentMax = data[i]; // O(1)
}
return currentmax; // O(1)
}
```
위 코드에 각 라인별 수행 속도를 다 더하면 `O(n) + 5O(1)`이다. 여기서 가장 높은 차수만 남겨 해당 알고리즘의 복잡도를 계산하면 O(n)이 된다.
일반적으로 빅오 표기법은 n의 가장 큰 지수만 고려한다. (총 연산 결과가 `3n^2 + 100n + 12345` 인 알고리즘은 **O(n^2)**로 표현)
### 5.4 Big-Oh, Theta, Omega 노테이션
빅오 노테이션과 비슷한 몇 가지 표현식들이 더 있긴한데, 이거는 그냥 읽어보고 잊어버리자~
입력 값의 크기가 `n`인 알고리즘의 수행시간을 `T(n)`이라고 정의 할 때, O, Θ, Ω 노테이션은 아래와 같은 의미를 갖는다.
```
// T(n) is O(f(n))
growth rate of T(n) <= growth rate of f(n)
//T(n) is Ω(f(n))
growth rate of T(n) >= growth rate of f(n)
// T(n) is Θ(f(n))
growth rate of T(n) == growth rate of f(n)
```
## 요약
1. 알고리즘이란, 문제해결 방법이다.
2. 좋은 알고리즘은 효율적이다.
3. 자료구조는 좋은 알고리즘을 만드는 것을 돕는다.
4. 알고리즘 효율성은 두 가지 방법으로 분석가능하다.
- 실험적 분석
- 이론적 분석
5. 이론적 분석 시 빅오 표기법을 통해 복잡도를 측정한다.
- O(n^2 + 100n + 1000) -> O(n^2)
Challenge
개념 실습! 학습 내용을 진짜 내 것으로 만들기!