introduction to algorithms 01강

3 minute read

교재 : introduction to algorithms 강의 : 링크

알고리즘의 분석과 디자인

성능

알고리즘 분석은 컴퓨터 프로그램 성능과 리소스 사용에 대한 이론적인 학문이다. 분석하면서 많은 기술들을 익혀야 하며 어떤 알고리즘이 application들을 가장 빠르고 리소스 사용을 최적으로 할지 고민하여 나온 것이 디자인이다. 이렇게 우린 알고리즘을 분석하고 효율적으로 디자인을 하는데 있어 성능에 초점을 맞춘다.

What’s more important than performance?

프로그래머의 입장이라면…
• 프로그래머의 시간^{programmer time} : 프로그래밍할 때 프로그래머의 시간 • 모듈방식^modularity
• 유지^{maintainability}

사용자의 입장이라면…
• 사용하기 쉬움^{user-friendliness} : 정량적인 기준은 없다.
• 확장성^{extensibility, scalability} • 보안^security
• 정확성^correctness
• 간단함^simplicity
• 기능성^{functionality}

하지만 이 모든것들과 연결하여 설명할 수 있는 것이 성능이다.

Why is performance important?(=Why study algorithm performance?)

실시간 요구^{real-time requirements}가 있을 때, 성능은 그것이 실현 가능한지 않은지를 구분해준다.
한번도 해본적 없는 일에 대해 알고리즘으로 그 일이 가능한지 불가능한지 말해줄 수 있다. 불가능하다면 시간이 너무 오래 걸려서(시간 복잡도) 안될 것 같다 라는 의견이나 다른 의견들이 제시될 수 있겠다.
알고리즘이 프로그램이 어떻게 움직이는지에 대해 말해주는 언어이기 때문이다.
알고리즘은 컴퓨터 과학 전반에 걸쳐 사용되는 전문적인 언어이고 이론적인 언어이다. 왜냐하면 알고리즘은 프로그램의 움직임을 깔끔하게 이해하는 방법이며 성능을 이해하는 좋은 방법이다.
돈과 연관되어 있다.
우리는 성능에 돈의 가치(비용)를 부여한다. 고사양의 노트북을 비싸지만 구매하는 이유이다.(물론 단순한 사치품과는 다르다.) 높은 성능의 제품은 비싼 돈의 가치가 있다고 보편적으로 판단된다. 우리가 쉽게 수량화할 수 있는 것이기 때문이다.
it’s tons of fun!
지극히 교수님 피셜이다. 알고리즘으로 높은 성능을 구현하면 빠르기 때문이다. 우리는 빠른것을 좋아한다. 8282

알고리즘 분석

“수행시간”과 “입력크기”를 살펴본다.

수행시간은 입력에 의해 결정된다. 입력 수열이 어느 정도 정렬되어 있느냐에 따라 수행시간이 달라질 수도 있다.
일반적으론 입력크기가 커질수록 수행시간이 증가한다.

입력크기

입력크기는 단순히 n개야 라고 할 순 없다. 주어진 문제에 따라 다르다. 가장 일반적인 기준은 입력 항목의 개수이다.
알고리즘의 입력이 그래프인 경우 : 노드의 개수, 간선의 개수

수행시간

알고리즘의 기본 연산 개수 또는 실행된 단계^level의 횟수
의사코드의 각 행을 수행하는 데 상수 시간이 소요된다. $i$ 행을 실행하는 데는 $c_i$ 시간이 걸린다고 가정한다.
각 명령문의 실행에 따른 비용과 실행 횟수를 고려해 살펴본다. 그래서 수행 시간 $ T(n) $을 구하는 것은 비용과 횟수의 곱을 합하면 된다.
최악의 상황을 고려한다.

삽입정렬^{insertion sorting}

삽입정렬은 점진적인 방법^{Asymptotic Analysis}
수행시간: 삽입정렬에서는 입력 크기가 n이므로 수행시간은 n값에 의해 결정된다.
수행시간(최악의 경우^{upper bound}): $\theta \left( n^2 \right)$

의사코드^pseudocode

Insert-sort(A,n) -> A[1,…,n]
for j <- 2 to A.length
Do key <- A[j]
i <- j-1
While i>0 and A[i]>key
Do A[i+1] <- A[i]
i <- i-1
A[i+1] = key

병합정렬^{Merge sorting}

분할정복 접근법

재귀적 프로그램^{recursive program} 중 하나이다. 자기 자신을 반복적^recurrence으로 여러 번 호출함으로써 연관된 문제를 다룬다.
- 분할 : 현재의 문제를 같은 문제를 다루는 다수의 부분문제로 분할한다.
- 정복 : 부분 문제를 재귀적으로 풀어서 정복한다.
- 결합 : 부분 문제의 해를 결합하여 원래 문제의 해가 되도록 만든다. 위의 말만 보면 이해가 잘 안되고 어렵다. 쉽게 이해하는 방법으로 병합 정렬을 예로 들어보자.
병합 정렬
- 분할 : 정렬할 n개 원소의 배열을 $\frac{n}{2}$개씩 부분 수열 두 개로 분할한다.
- 정복 : 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다.
- 결합 : 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만든다.(핵심)
  정렬할 수열의 크기가 1이 되면 -> 종료 조건

병합정렬 알고리즘

A : 배열
p,q,r : 인덱스 $p \lt q \lt r$

의사코드

n_1 = q-p+1
n_2 = r-q
배열 L[1..n_1+1]과 R[1..n_2+1]을 생성한다.
for i=1 to n_1
L[i] = A[p+i-1]
for j=1 to n_2
R[j] = A[q+j]
L[n_1+1] = $\infty$
R[n_2+1] = $\infty$
i=1 j=1 for k=p to r if L[i] $\lt$ R[j] A[k] = L[i] i = i+1 else A[k] = R[j] j = j+1

복잡도

알고리즘의 분석 방법

최대시간 : 어떠한 입력 사이즈에 대한 최대시간.
알고리즘의 러닝 타임에서 상한값^{upper bound}. 이 이상의 시간은 걸리지 않는다는 것을 보장하기 위해 알고자 한다. 이는 한 알고리즘의 입력값n에 대한 함수이다. 하나밖에 없기 때문이다.
T(n) : 사이즈가 n인 입력 전반적으로 기대되는 시간.
기대되는 시간은 하나의 입력 값을 넣었을 때의 시간 / 모든 입력 값을 넣었을 때의 시간이다.

점근적 분석 방법^{Asymtotic Notation}

세타 표기법 : $3n^3 = 90n^2 - 5n + 6046$ 에서 낮은 차수의 항, 최고차 항으로 만든다. $ \theta\left(n^3\right) $
빅오 표기법 :
오메가 표기법 :

Share on

Twitter Facebook LinkedIn

인공지능 대학원 준비생