알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 2 2019년 봄학기 강원대학교 컴퓨터과학전공 문양세

프로그램과 알고리즘 순차검색과 이진검색 피보나찌 수 구하기 알고리즘 분석 차수 (O, , ) – Part 2 강의 내용

차수(Order)? 알고리즘이 얼마나 복잡한지를 정량적으로 다루기 위한 개념 알고리즘: 효율, 분석, 차수 – Part 2 알고리즘이 얼마나 복잡한지를 정량적으로 다루기 위한 개념 알고리즘 A의 시간 복잡도가 0.1n2이고, 알고리즘 B의 시간 복잡도가 1000n이라 하자. 그렇다면, 어떤 알고리즘이 더 좋은가? 항시 어떤 알고리즘이 좋다고 이야기할 수는 없다. 예를 들어, n이 100 이하라면 알고리즘 A가 시간이 적게 걸리고, n이 10000 이상이라면 알고리즘 B가 시간이 적게 걸린다. 그래도…, 어떤 알고리즘이 효율적인지 척도가 있어야 하지 않나?  일반적으로, 입력 크기 n이 매우 크다(커진다)고 가정하고 비교한다.

(lg n): 로그(logarithmic) (n): 1차(linear) (n lg n) 대표적인 복잡도 카테고리 알고리즘: 효율, 분석, 차수 – Part 2 (lg n): 로그(logarithmic) (n): 1차(linear) (n lg n) (n2): 2차(quadratic) (n3): 3차(cubic) (2n): 지수(exponential) (n!): factorial

시간 복잡도 비교 예제 알고리즘: 효율, 분석, 차수 – Part 2 복잡도가 2차 이하로 구성된 경우, 2차 항이 궁극적으로 지배한다. n 0.1n2 0.1n2+n+100 10 120 20 40 160 50 250 400 100 1,000 1,200 100,000 101,100

복잡도 함수의 증가율 알고리즘: 효율, 분석, 차수 – Part 2

시간 복잡도별 실제 실행 시간 비교 알고리즘: 효율, 분석, 차수 – Part 2

차수의 정밀한 소개 O(f(n)), (f(n)), (f(n))? 그래프 보고, 단번에 이해하기… 알고리즘: 효율, 분석, 차수 – Part 2 O(f(n)), (f(n)), (f(n))? 그래프 보고, 단번에 이해하기…

Big O 표기법 (1/2) 정의: 점근적 상한(Asymptotic Upper Bound) 알고리즘: 효율, 분석, 차수 – Part 2 정의: 점근적 상한(Asymptotic Upper Bound) 주어진 복잡도 함수 f(n)에 대해서 g(n)(f(n)) 이면 다음을 만족한다. n  N인 모든 정수 n에 대해서, g(n)  c  f(n)이 성립하는 실수 c  0와 음이 아닌 정수 N이 존재한다. g(n)  (f(n)) 읽는 방법: g(n)은 f(n)의 Big 이다.

Big O 표기법 (2/2) 어떤 함수 g(n)이(n2)에 속한다는 말은 어떤 알고리즘의 시간복잡도가 (f(n))이라면 알고리즘: 효율, 분석, 차수 – Part 2 어떤 함수 g(n)이(n2)에 속한다는 말은 함수 g(n)는 궁극에 가서는 (즉, 어떤 임의의 N값보다 큰 값에 대해서는) 어떤 2차 함수 cn2 보다는 작은 값을 가지게 된다는 것을 뜻한다. (그래프 상에서는 아래에 위치한다는 의미이다.) 다시 말해서, 그 함수 g(n)은 어떤 2차 함수 cn2 보다는 궁극적으로 좋다고 (기울기가 낮다고) 말할 수 있다. 어떤 알고리즘의 시간복잡도가 (f(n))이라면 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 느려도 cf(n)보다는 빠르다. (궁극적으로, cf(n)이 상한이다.)

Big O 표기법 예제 알고리즘: 효율, 분석, 차수 – Part 2 n2+10n  (n2) ? (1) n  10인 모든 정수 n에 대해서 n2+10n  2n2 이 성립한다. 그러므로, c = 2와 N = 10을 선택하면, “Big  ”의 정의에 의해서 n2+10n  (n2)이라고 결론지을 수 있다. (2) n  1인 모든 정수 n에 대해서 n2+10n  n2+10n2 = 11n2 이 성립한다. 그러므로, c = 11와 N = 1을 선택하면, “Big  ”의 정의에 의해서 n2+10n  (n2)이라고 결론지을 수 있다.  Big O를 보이는데 단지 한 가지 해답이 있는 것이 아니다. 적당히 큰 N과 c를 선택하여 보이면 된다.

2n2과 n2 + 10n의 비교 알고리즘: 효율, 분석, 차수 – Part 2

5n2  (n2) ? c=5와 N=0을 선택하면, n  0인 모든 정수 n에 대해서 5n2  5n2이 성립한다. Big O 표기법 다른 예제 (1/2) 알고리즘: 효율, 분석, 차수 – Part 2 5n2  (n2) ? c=5와 N=0을 선택하면, n  0인 모든 정수 n에 대해서 5n2  5n2이 성립한다. ? n  0인 모든 정수 n에 대해서 이 성립한다. 그러므로, c=1/2와 N=0을 선택하면, T(n) (n2)이라고 결론지을 수 있다. n2  (n2+10n) ? n  0인 모든 정수 n에 대해서, n2  1 (n2+10n)이 성립한다. 그러므로, c=1와 N=0을 선택하면, n2  (n2+10n)이라고 결론지을 수 있다.

Big O 표기법 다른 예제 (2/2) 알고리즘: 효율, 분석, 차수 – Part 2 n  (n2) ? n  1인 모든 정수 n에 대해서, n  1n2 이 성립한다. 그러므로, c=1와 N=1을 선택하면, n (n2)이라 결론지을 수 있다. n3  (n2) ? n  N인 모든 n에 대해서 n3  cn2 이 성립하는 c와 N값은 존재하지 않는다. 즉, 양변을 n2으로 나누면, n  c 가 되는데 c를 아무리 크게 잡더라도 그 보다 더 큰 n이 존재한다.

O(n2)에 속하는 함수들 알고리즘: 효율, 분석, 차수 – Part 2

 표기법 (1/2) 정의: 점근적 하한(Asymptotic Lower Bound) 알고리즘: 효율, 분석, 차수 – Part 2 정의: 점근적 하한(Asymptotic Lower Bound) 주어진 복잡도 함수 f(n)에 대해서 g(n)  (f(n))이면 다음을 만족한다. n  N인 모든 정수 n에 대해서 g(n)  c  f(n)이 성립하는 실수 c  0와 음이 아닌 정수 N이 존재한다. g(n)  (f(n)) 읽는 방법: g(n)은 f(n)의 오메가(omega)이다.

 표기법 (2/2) 어떤 함수 g(n)이 (n2)에 속한다는 말은 알고리즘: 효율, 분석, 차수 – Part 2 어떤 함수 g(n)이 (n2)에 속한다는 말은 그 함수는 궁극에 가서는 (즉, 어떤 임의의 N 값보다 큰 값에 대해서는) 어떤 2차 함수 cn2 의 값보다는 큰 값을 가지게 된다는 것을 뜻한다. (그래프 상에서는 윗 부분에 위치한다.) 다시 말해서, 그 함수 g(n)은 어떤 2차 함수 cn2 보다는 궁극적으로 나쁘다고 (기울기가 높다고)말할 수 있다. 어떤 알고리즘의 시간복잡도가 (f(n))이라면, 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 빨라도 cf(n)보다는 느리다. (궁극적으로, c f(n)이 하한이다.)

 표기법의 예제 (1/3) 알고리즘: 효율, 분석, 차수 – Part 2 n2 +10n  (n2) ? n  0인 모든 정수 n에 대해서 n2+10n  n2 이 성립한다. 그러므로, c = 1와 N = 0을 선택하면, n2 +10n  (n2)이라 결론지을 수 있다. 5n2  (n2) ? n  0인 모든 정수 n에 대해서, 5n2  1n2 이 성립한다. 그러므로, c=1와 N=0을 선택하면, 5n2  (n2)이라 할 수 있다.

 표기법의 예제 (2/3) 알고리즘: 효율, 분석, 차수 – Part 2 ? n  2인 모든 n에 대해서 이 성립한다. 그러므로, n  2인 모든 n에 대해서 이 성립한다. 따라서 과 N = 2를 선택하면, 이라 할 수 있다. ? n  1인 모든 정수 n에 대해서, 이 성립한다. 그러므로, c = 1와 N = 1을 선택하면, 이라 할 수 있다.

 표기법의 예제 (3/3) 알고리즘: 효율, 분석, 차수 – Part 2 n  (n2) ? 모순유도에 의한 증명(Proof by contradiction): 이라 가정하자. 그러면 n  N인 모든 정수 n에 대해서, 이 성립하는 실수 c > 0, 그리고 음이 아닌 정수 N이 존재한다. 위의 부등식의 양변을 cn으로 나누면 가 된다. 그러나 이 부등식은 절대로 성립할 수 없다. (주어진 어떤 수(1/c)보다 큰 수가 항시 존재하기 때문이다.) 따라서 위의 가정은 모순이다.

(n2)에 속하는 함수들 알고리즘: 효율, 분석, 차수 – Part 2

 표기법 (1/2) 정의: (Asymptotic Tight Bound) 알고리즘: 효율, 분석, 차수 – Part 2 정의: (Asymptotic Tight Bound) 복잡도 함수 f(n)에 대해서 (f(n)) = O(f(n))  (f(n))의 관계가 성립한다. 다시 말하면, (f(n))은 다음을 만족하는 복잡도 함수 g(n)의 집합이다. 즉, n  N 인 모든 정수 n에 대해서 c  f(n)  g(n)  d  f(n)이 성립하는 실수 c  0와 d  0, 그리고 음이 아닌 정수 N이 존재한다. 참고: g(n)  (f(n))은 “g(n)은 f(n)의 차수(order)”라고 한다. 예: 은 O(n2)이면서 (n2)이다. 따라서 이다.

 표기법 (2/2) 알고리즘: 효율, 분석, 차수 – Part 2

(n2)에 속하는 함수들 알고리즘: 효율, 분석, 차수 – Part 2

Small O(o) ? Small 는 복잡도 함수 끼리의 관계를 나타내기 위한 표기법이다. 알고리즘: 효율, 분석, 차수 – Part 2 Small 는 복잡도 함수 끼리의 관계를 나타내기 위한 표기법이다. 자주 사용되지 않는 개념이므로, 본 강의에서 제외한다.

지수(exponential) 복잡도 함수가 모두 같은 카테고리 안에 있는 것은 아니다. 차수의 주요 성질 (1/2) 알고리즘: 효율, 분석, 차수 – Part 2 iff b > 1이고 a > 1이면, loga n  (logb n)은 항상 성립한다. 다시 말하면 로그(logarithm) 복잡도 함수는 모두 같은 카테고리에 속한다. 따라서 통상 (lg n)으로 표시한다. 지수(exponential) 복잡도 함수가 모두 같은 카테고리 안에 있는 것은 아니다. n!은 어떤 지수 복잡도 함수보다도 더 나쁘다.

복잡도 카테고리들은 다음 순서로 나열된다. 여기서 k>j>2이고 b>a>1이다. 차수의 주요 성질 (2/2) 알고리즘: 효율, 분석, 차수 – Part 2 복잡도 카테고리들은 다음 순서로 나열된다. 여기서 k>j>2이고 b>a>1이다.

Homework #2 알고리즘: 효율, 분석, 차수 – Part 2