Lecture1,2 - 알고리즘 설계와 분석의 기초(1)

---

알고리즘이란?

알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 체계적 으로 기술한 것을 말한다.

다음은 문제, 입출력 및 알고리즘에 대한 간단한 예시이다.

 

▪ 문제: 100명의 학생들의 시험점수 중 최대값을 찾으라

▪ 입력: 100명의 학생들의 시험점수

▪ 출력: 위 100개의 시험점수들 중 최대값

▪ 알고리즘: Algorithm maxScore(x[], n) {

                                                                      x[1...n]의 값을 차례대로 보면서 최대값을 계산 위에서 찾은 최대값을 반환

                                                                  }

 

또한 현존하는 어떤 알고리즘으로도 polynomial시간 내에 최적의 해를 구할 수 없는 "Travelling Salesman Problem"도 있다.

▪ 입력: 어떤 영업사원이 방문해야 할 고객 n명의 위치

▪ 출력: 모든 고객을 방문하고 돌아오는 가장 짧은 경로

▪ 알고리즘: 최적화된 알고리즘은 없지만 컴퓨터과학에서 유명한 문제인 만큼 다양한 장단점을 가진 알고리즘들이 개발되어있다.

 

알고리즘은 일반적으로 프로그래밍 언어와 유사한 의사코드(pseudocode)를 이용해 작성한다.

이 때, 알고리즘을 명확하게 기술하여야 하지만 프로그래밍 언어 레벨로 작성해버리면 변수 선언 등 알고리즘 레벨에서는 불필요한 코드까지 작성하게 되기 때문에 해당 알고리즘을 다양한 프로그래밍 언어로 구현할 수 있을 정도로 명확하면서 너무 세세한 부분까지는 작성하지 않도록 디테일을 조절해야 한다. 명확성을 해치지 않으면 일반언어의 활용도 무방하다.

---

알고리즘 분석

알고리즘 분석은 다음과 같은 두 가지 종류가 있다.

▪ 정확성(correctness) 분석 - 알고리즘이 주어진 문제의 요건을 만족하는지 분석하는 것을 의미한다.

▪ 효율성(efficiency) 분석 - 알고리즘이 얼마나 자원을 효율적으로 사용하는지 분석하는 것을 의미한다.

메모리 요구량이 너무 높다면 비현실적인 알고리즘일 수도 있으나, 일반적으로는 메모리를 좀 더 쓰더라도 시간 측면에서 더 효율적인 알고리즘이 더 좋은 알고리즘이라고 볼 수 있다.

알고리즘의 효율성 분석은 주어진 입력의 크기가 충분히 큰 경우에 대해 분석한다. 입력의 크기가 작은 경우에는 알고리즘의 효율성이 상대적으로 중요하지 않으므로 비효율적인 알고리즘도 무방할 수 있다. 반면에 입력의 크기가 큰 문제의 경우에는 알고리즘의 효율성에 따라 총 연산시간이 엄청나게 차이 날 수 있으므로 효율성이 굉장히 중요하다. 입력의 크기가 충분히 큰 경우에 대한 알고리즘 효율성 분석을 점근적 분석(asymptotic analysis)이라 한다.

 

알고리즘의 수행 시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현한다. 이때 입력의 크기는 보통 n으로 표현하며 입력의 크기가 무엇인지는 많은 경우에 자명하다.

-정렬: 정렬하고자 하는 개체의 개수

-탐색: 탐색하고자 하는 값을 포함하고 있는 자료 내의 값 개수

-도시 간의 최단 거리: 도시의 수 및 도로의 수

또한 알고리즘의 수행 시간을 좌우하는 기준은 다양하게 잡을 수 있으며 문제마다 다를 수 있다. 예를들어 for 루프의 반복횟수, 특정 알고리즘 행의 실행 횟수, 함수 호출횟수 등이 있다.

예시를 통해 분석법을 살펴보면 다음과 같다.

 

Ex1

n에 관계없이 상수시간이 소요되므로 big-O notation으로 분석해보면 O(1) 시간복잡도라고 할 수 있다.

 

Ex2

for문에 의해 n에 비례하는 다항시간이 걸린다고 분석할 수 있으므로 O(n) 시간복잡도라고 할 수 있다.

 

Ex3

이중 for문에 의해 n^2에 비례하는 다항시간이 걸린다고 분석할 수 있으므로 O(n^2) 시간복잡도라고 할 수 있다.

 

Ex4

이중 for문에 의해 n^2에 비례하는 다항시간이 걸리지만 이중 for문 내부의 함수가 이미 n에 비례하는 다항시간이 소요되므로 O(n^3) 시간복잡도라고 분석할 수 있다.

 

Ex5

재귀 함수이므로 함수 호출 수인 n에 비례한 다항시간이 걸리므로 O(n) 시간복잡도라고 분석할 수 있다.

 

---

점근적 표기법

점근적 표기법이란 lim(n→∞) f(n)와 같이 입력의 크기가 무한히 커질 때에 대해 각 함수의 대소에 대해 나타낸 것이다.

각 함수별 증가율 예시

 

 

n값 변화에 따른 각 함수별 값 비교

 

n값 변화에 따른 알고리즘별 수행 시간 예시

---

Big O notation

Formal definition:  O(g(n)) = { f(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0 , cg(n) ≥ f(n) }

▪ f(n) ∈ O(g(n)을 관행적으로 f(n) = O(g(n))이라고 쓴다.

직관적으로 보면 f(n) = O(g(n)) ⇒ f 는 g보다 빠르게 증가하지 않는다는 뜻이다.

 

O(n^2)인 함수들의 예시

▪ 3n 2 + 2n          ▪ 7n 2 – 100n         ▪ nlogn + 5n

 

Big O notation을 쓸 때는 알 수 있는 한 최대한 tight하게 표현해주도록 해야한다. 예를들어 nlogn + 5n = O(nlogn) 인데 굳이 O(n^2)으로 쓸 필요 없는 것이다. 왜냐하면 엄밀하지 않으면 그만큼 함수의 점근적 대소 비교에 대한 정보 손실이 일어나게 되기 때문이다.

 

f(x) = O(g(x)) 임을 증명하려면 엄밀한 big O notation 조건을 만족하는 c, k값을 찾으면 된다.

 

예시를 통해 살펴보자.

 

f(x) = x^2+2x+1 is O(x^2)임을 증명하라.

sol) x > 1일 때, x < x^2 및 1 < x^2 이므로 0 <= x^2+2x+1 <= x^2+2x^2+x^2 <= 4x^2

따라서 c=4, n0=1로 잡으면 big O notation의 정의를 충족한다.

---

대표적인 복잡도

*은 10^100년 이상이 걸리는 시간을 의미한다.

---