알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기

Presentation on theme: "알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기"— Presentation transcript:

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

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

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

4 (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

5 시간 복잡도 비교 예제 알고리즘: 효율, 분석, 차수 – 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

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

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

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

9 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 이다.

10 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)이 상한이다.)

11 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를 선택하여 보이면 된다.

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

13 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)이라고 결론지을 수 있다.

14 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이 존재한다.

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

16  표기법 (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)이다.

17  표기법 (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)이 하한이다.)

18  표기법의 예제 (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)이라 할 수 있다.

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

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

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

22  표기법 (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)이다. 따라서 이다.

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

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

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

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

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

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