2016 년 봄학기 강원대학교 컴퓨터과학전공 문양세 이산수학 (Discrete Mathematics) 알고리즘과 복잡도 (Algorithms and Complexity)

Discrete Mathematics by Yang-Sae Moon Page 2 강의 내용 알고리즘 (Algorithms) 함수의 증가 (Growth of Functions) 알고리즘 복잡도 (Algorithm Complexity) Algorithms and Complexity

Discrete Mathematics by Yang-Sae Moon Page 3 Algorithms The foundation of computer programming. ( 컴퓨터 프로그래밍의 기초 / 기반이다.) Most generally, an algorithm just means a definite procedure for performing some sort of task. ( 알고리즘은 주어진 일을 수행하기 위한 정의된 절차를 의미한다.) A computer program is simply a description of an algorithm in a language precise enough for a computer to understand. ( 컴퓨터 프로그램이란 정의된 알고리즘을 컴퓨터가 이해할 수 있는 언어 로 정확하게 기술한 것에 불과하다.) We say that a program implements (or “is an implementation of”) its algorithm. ( 프로그램은 알고리즘을 “ 구현한 것이다 ” 라고 이야기한다.) Algorithms

Discrete Mathematics by Yang-Sae Moon Page 4 Programming Languages Some common programming languages: Newer: Java, C, C++, Visual Basic, JavaScript, Perl, Tcl, Pascal Older: Fortran, Cobol, Lisp, Basic Assembly languages, for low-level coding. In this class we will use an informal, Pascal-like “pseudo- code” language. You should know at least 1 real language! Algorithms

Discrete Mathematics by Yang-Sae Moon Page 5 Algorithm Example (in English) Task: Given a sequence {a i }=a 1,…,a n, a i  N, say what its largest element is. ( 주어진 sequence 에서 가장 큰 수는 ?) Algorithm in English Set the value of a temporary variable v to a 1 ’s value. Look at the next element a i in the sequence. If a i >v, then re-assign v to the number a i. Repeat previous 2 steps until there are no more elements in the sequence, & return v. Algorithms

Discrete Mathematics by Yang-Sae Moon Page 6 Executing an Algorithm When you start up a piece of software, we say the program or its algorithm are being run or executed by the computer. ( 소프트웨어를 시작할 때, 우리는 프로그램 혹은 알고리즘을 실행한다 ( 혹은 돌린다 ) 라고 이야기한다.) Given a description of an algorithm, you can also execute it by hand(?), by working through all of its steps on paper. ( 알고리즘이 있으면, 종이에 손으로 써 가면서 이를 수행할 수도 있다.) Before ~WWII, “computer” meant a person whose job was to run algorithms! (2 차 대전 이전에, 컴퓨터는 알고리즘을 수행하는 사람을 의미했다 !) Algorithms

Discrete Mathematics by Yang-Sae Moon Page 7 Execute the Max Algorithm Let {a i }=7,12,3,15,8. Find its maximum… by hand. Set v = a 1 = 7. Look at next element: a 2 = 12. Is a 2 >v? Yes, so change v to 12. Look at next element: a 3 = 3. Is 3>12? No, leave v alone…. Is 15>12? Yes, v=15… Algorithms

Discrete Mathematics by Yang-Sae Moon Page 8 Algorithm Characteristics ( 알고리즘의 특성 ) (1/2) Some important features of algorithms: Input( 입력 ): Information or data that comes in. Output( 출력 ): Information or data that goes out. Definiteness( 명확성 ): Precisely defined. ( 각 단계는 명확하게 정의되어야 한다.) Correctness( 정확성 ): Outputs correctly relate to inputs. ( 입력 값의 각 집합에 대해서 정확한 출력 값을 만들어야 한다.) Finiteness( 유한성 ): Won’t take forever to describe or run. Algorithms

Discrete Mathematics by Yang-Sae Moon Page 9 Algorithm Characteristics ( 알고리즘의 특성 ) (2/2) Some important features of algorithms ( 계속 ): Effectiveness( 효율성 ): Individual steps are all do-able. ( 각 단계는 유한한 양의 시간에 수행되어야 한다.) Generality( 일반성 ): Works for many possible inputs. ( 특정한 입력이 아닌 모든 가능한 입력에 대해서 동작하여야 한다.) Algorithms

Discrete Mathematics by Yang-Sae Moon Page 10 Pseudocode Language procedure name(argument: type) variable := expression informal statement begin statements end {comment} if condition then statement [else statement] for variable := initial value to final value statement while condition statement procname(arguments) Not defined in book: return expression Algorithms

Discrete Mathematics by Yang-Sae Moon Page 11 procedure procname(arg: type) Declares that the following text defines a procedure named procname that takes inputs (arguments) named arg which are data objects of the type type. Example: procedure maximum(L: list of integers) [statements defining maximum…] Algorithms

Discrete Mathematics by Yang-Sae Moon Page 12 variable := expression An assignment statement evaluates the expression, then reassigns the variable to the value that results. Example: v := 3x+7 (If x is 2, changes v to 13.) In pseudocode, the expression might be informal: x := the largest integer in the list L Algorithms

Discrete Mathematics by Yang-Sae Moon Page 13 Informal Statement Sometimes we may write an informal statement, if the meaning is still clear and precise: “swap x and y.” Keep in mind that real programming languages never allow this. ( 궁극적으로는 알고리즘을 쓰고 이를 구현해야 한다.) When we ask for an algorithm to do so-and-so, writing “Do so-and-so” isn’t enough! (“x 를 찾는 알고리즘을 기술하라 ” 했는데, “find x” 라 하는 것은 충분치 않다 !) Break down algorithm into detailed steps. Algorithms

Discrete Mathematics by Yang-Sae Moon Page 14 begin statements end Groups a sequence of statements together: begin statement 1 statement 2 … statement n end Allows sequence to be used like a single statement. Might be used: After a procedure declaration. In an if statement after then or else. In the body of a for or while loop. Algorithms

Discrete Mathematics by Yang-Sae Moon Page 15 { comment } Not executed (does nothing). Natural-language text explaining some aspect of the procedure to human readers. (Reader 의 이해 도모 ) Also called a remark in some real programming languages. Example: {Note that v is the largest integer seen so far.} Algorithms

Discrete Mathematics by Yang-Sae Moon Page 16 If condition then statement Evaluate the propositional expression condition. If the resulting truth value is true, then execute the statement; otherwise, just skip on ahead to the next statement. ( 조건이 true 일 때만 문장을 수행한다.) Variant: if cond then stmt1 else stmt2 Like before, but iff truth value is false, executes stmt2. Algorithms

Discrete Mathematics by Yang-Sae Moon Page 17 while condition statement (1/2) Evaluate the propositional expression condition. If the resulting value is true, then execute statement. Continue repeating the above two actions over and over until finally the condition evaluates to false; then go on to the next statement. ( 조건이 true 인 한 문장을 반복하여 수행한다.) Algorithms

Discrete Mathematics by Yang-Sae Moon Page 18 while comment statement (2/2) Also equivalent to infinite nested ifs, like so: (if 를 무한히 써서 구현할 수도 있다 …. 설마 ~) if condition begin statement if condition begin statement …(continue infinite nested if’s) end end Algorithms

Discrete Mathematics by Yang-Sae Moon Page 19 for var := initial to final stmt Initial is an integer expression. Final is another integer expression. Repeatedly execute stmt, first with variable var := initial, then with var := initial+1, then with var := initial+2, etc., then finally with var := final. What happens if stmt changes the value that initial or final evaluates to? For can be exactly defined in terms of while, like so: begin var := initial while var  final begin stmt var := var + 1 end end Algorithms

Discrete Mathematics by Yang-Sae Moon Page 20 procedure(argument) A procedure call statement invokes the named procedure, giving it as its input the value of the argument expression. Various real programming languages refer to procedures as functions (since the procedure call notation works similarly to function application f(x)), or as subroutines, subprograms, or methods. Algorithms

Discrete Mathematics by Yang-Sae Moon Page 21 Max Procedure in Pseudocode Rewrite “finding maximum number” in pseudocode. procedure max(a 1, a 2, …, a n : integers) v := a 1 {largest element so far} for i := 2 to n {go thru rest of elems} if a i > v then v := a i {found bigger?} {at this point v’s value is the same as the largest integer in the list} return v Algorithms procedure max(a 1, a 2, …, a n : integers) v := a 1 for i := 2 to n if a i > v then v := a i return v

Discrete Mathematics by Yang-Sae Moon Page 22 Inventing an Algorithm Requires a lot of creativity and intuition. Like writing proofs. We can’t give you an algorithm for inventing algorithms. Just look at lots of examples… [ 많은 예를 보세요 …] And practice (preferably, on a computer) [ 연습을 많이 하세요 …] And look at more examples… [ 좀 더 많은 예를 보세요 …] And practice some more… etc., etc. [ 좀 더 많은 연습을 하세요 …] Algorithms

Discrete Mathematics by Yang-Sae Moon Page 23 Searching Algorithm ( 탐색 알고리즘 ) Problem of searching an ordered list. ( 정렬된 리스트에서 주어진 값을 찾아내는 검색을 수행하는 문제 ) Given a list L of n elements that are sorted into a definite order (e.g., numeric, alphabetical), And given a particular element x, Determine whether x appears in the list, and if so, return its index (position) in the list. Problem occurs often in many contexts. ( 여러 분이 Programming 을 하는 한 수십 번 이상 마주치는 문제임 !) Let’s find an efficient algorithm! Algorithms

Discrete Mathematics by Yang-Sae Moon Page 24 Linear Search ( 선형 탐색 ) 리스트의 첫 번째 원소부터 차례대로 검색하는 방법 예 : Find ‘12’ in {3, 6, 9, 12, 15, 18, 21, 24} procedure linear search (x: integer, a 1, a 2, …, a n : distinct integers) i := 1 while (i  n  x  a i ) i := i + 1 if i  n then location := i else location := 0 return location {index or 0 if not found} Linear search 는 ordered list( 정렬된 상태 ) 뿐 아니라 unordered list( 정렬 되지 않은 상태 ) 에서도 바르게 동작한다. Algorithms

Discrete Mathematics by Yang-Sae Moon Page 25 Binary Search ( 이진 탐색 ) (1/2) Basic idea: On each step, look at the middle element of the remaining list to eliminate half of it. ( 리스트의 중간에 위치한 값과 비교하여, 작은 값들을 가지는 리스트 혹은 큰 값 들을 가지는 리스트 중에서 한쪽 부분에 대해서만 검사를 진행한다.) 예 : Find ‘18’ in { 3, 6, 9, 12, 15, 18, 21, 24 } <x<x>x>x<x<x<x<x Algorithms

Discrete Mathematics by Yang-Sae Moon Page 26 Binary Search ( 이진 탐색 ) (2/2) procedure binary search (x:integer, a 1, a 2, …, a n : distinct integers) i := 1 {left endpoint of search interval} j := n {right endpoint of search interval} while i 1 item} m :=  (i+j)/2  {midpoint} if x>a m then i := m+1 else j := m end if x = a i then location := i else location := 0 return location Binary search 는 ordered list( 정렬된 상태 ) 에서만 바르게 동작할 뿐 unordered list( 정렬되지 않은 상태 ) 에서는 바르게 동작하지 않는다. Algorithms

Discrete Mathematics by Yang-Sae Moon Page 27 Sorting Algorithm ( 정렬 알고리즘 ) Sorting is a common operation in many applications. (Programming 을 하는 한 Search 다음으로 많이 마주치는 문제임 !) E.g. spreadsheets and databases It is also widely used as a subroutine in other data- processing algorithms. Two sorting algorithms shown in textbook: Bubble sort Insertion sort There are more than 15 different sorting algorithms! (“The Art of Computer Programming” by Donald Knuth.) However, these are not very efficient, and you should not use them on large data sets! Algorithms

Discrete Mathematics by Yang-Sae Moon Page 28 Bubble Sort – Example Sort L = {3, 2, 4, 1, 5} nd pass1 st pass 3 rd pass4 th pass Algorithms

Discrete Mathematics by Yang-Sae Moon Page 29 Bubble Sort – Algorithm procedure bubble sort(a 1, a 2, …, a n : real numbers with n  2) for i := 1 to n - 1 for j := 1 to n - i if a j > a j+1 then interchange a j and a j+1 {a 1, a 2, …, a n is in increasing order.} Algorithms

Discrete Mathematics by Yang-Sae Moon Page 30 Insertion Sort procedure insertion sort(a 1, a 2, …, a n : real numbers with n  2) for j := 2 to n i := 1 while a j > a i {find a proper position of a j } i := i + 1 m := a j for k := 0to j – i – 1 {insert a j into the proper position} a j-k := a j-k-1 a i := m {a 1, a 2, …, a n is in increasing order.} Algorithms

Discrete Mathematics by Yang-Sae Moon Page 31 Greedy Algorithm 최적의 알고리즘 (optimal algorithm) 을 찾기가 어렵다 ?  알고리즘의 각 단계에서 최선을 선택을 수행하는 Greedy algorithm 을 사용할 수 있다. Greedy algorithm 은 최적일 수도 있다. 최적임을 보이기 위해서는 증명이 필요하고, 최적이 아님을 보이기 위해서는 반례 (counterexample) 를 든다. 예제 25, 10, 5, 1 센트의 동전이 있을 때, 동전의 수를 최소화하면서 67 센트의 거스 름돈을 만들어라. −25 센트 동전을 선택한다.(42 센트 남음 ) −25 센트 동전을 선택한다.(17 센트 남음 ) −10 센트 동전을 선택한다.(7 센트 남음 ) −5 센트 동전을 선택한다.(2 센트 남음 ) −1 센트 동전을 선택한다.(1 센트 남음 ) Algorithms

Discrete Mathematics by Yang-Sae Moon Page 32 강의 내용 알고리즘 (Algorithms) 함수의 증가 (Growth of Functions) 알고리즘 복잡도 (Algorithm Complexity) Algorithms and Complexity

Discrete Mathematics by Yang-Sae Moon Page 33 Orders of Growth – Introduction For functions over numbers, we often need to know a rough measure of how fast a function grows. ( 과연 함수는 얼마나 빨리 증가하는가 ?) If f(x) is faster growing than g(x), then f(x) always eventually becomes larger than g(x) in the limit (for large enough values of x). (f(x) 가 g(x) 보다 빨리 증가한다면, 궁극적으로 f(x) 의 값이 g(x) 의 값보다 커진다.) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 34 Orders of Growth – Motivation Suppose you are designing a web site to process user data. Suppose database program A takes f A (n)=30n+8 microseconds to process any n records, while program B takes f B (n)=n 2 +1 microseconds to process the n records. Which program do you choose, knowing you’ll want to support millions of users? Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 35 Visualizing Orders of Growth On a graph, as you go to the right, a faster growing function eventually becomes larger... f A (n)=30n+8 Increasing n  f B (n)=n 2 +1 Value of function  Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 36 Concept of Orders of Growth We say f A (n)=30n+8 is order n, or O(n). It is, at most, roughly proportional to n. f B (n)=n 2 +1 is order n 2, or O(n 2 ). It is roughly proportional to n 2. Any O(n 2 ) function is faster-growing than any O(n) function. For large numbers of user records, the O(n 2 ) function will always take more time. Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 37 Definition: O(g), at most order g Let g be any function R  R. Define “at most order g”, written O(g), to be: {f:R  R |  c,k:  x>k: f(x)  cg(x)}. “Beyond some point k, function f is at most a constant c times g (i.e., proportional to g).” (x > k 일 때, f(x)  cg(x) 를 만족하는 c, k 가 존재하면, f 는 O(g) 라 한다.) “f is at most order g”, or “f is O(g)”, or “f=O(g)” all just mean that f  O(g). Sometimes the phrase “at most” is omitted. ( 일반적으로 그냥 “ 오더 g” 라 이야기한다.) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 38 Points about the Definition Note that f is O(g) so long as any values of c and k exist that satisfy the definition. But: The particular c, k, values that make the statement true are not unique: Any larger value of c and/or k will also work. ( 조건을 만족하는 c, k 는 여러 개 있을 수 있다.) You are not required to find the smallest c and k values that work. (Indeed, in some cases, there may be no smallest values!) ( 조건을 만족하는 가장 작은 c, k 를 찾을 필요는 없다. 보여주기만 하면 된다.) However, you should prove that the values you choose do work. ( 증명하기 위해서는 만족하는 c, k 를 하나는 찾아야 한다.) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 39 “Big-O” Proof Example Show that 30n+8 is O(n). Show  c,k:  n>k: 30n+8  cn. Let c=31, k=8. Assume n>k(=8). Then cn = 31n = 30n + n > 30n+8, so 30n+8 < cn. Show that n 2 +1 is O(n 2 ). Show  c,k:  n>k: n 2 +1  cn 2. Let c=2, k=1. Assume n>1. Then cn 2 = 2n 2 = n 2 +n 2 > n 2 +1, or n 2 +1< cn 2. Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 40 Big-O Example, Graphically Note 30n+8 isn’t less than n anywhere (n>0). It isn’t even less than 31n everywhere. But it is less than 31n everywhere to the right of n=8. E.g., c = 31, k = 8 n>k=8  Increasing n  Value of function  n 30n+8 cn = 31n 30n+8  O(n) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 41 Examples of Big-O (1/2) f(x) = a n x n + a n-1 x n-1 + … + a 1 x + a 0  |a n |x n + |a n-1 |x n-1 + … + |a 1 |x + |a 0 | = x n (|a n | + |a n-1 |/x + … + |a 1 |/x n-1 + |a 0 |/x n )  x n (|a n | + |a n-1 | + … + |a 1 | + |a 0 |) = cx n = O(x n ) f(n) = … + n  n + n + n + … + n = n 2 = O(n 2 ) c Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 42 Examples of Big-O (2/2) f(n) = n! f(n)= n! = n∙(n-1)∙(n-2)∙…∙3∙2∙1  n∙n∙n∙…∙n∙n∙n = n n = O(n n ) f(n) = log(n!)  log(n n ) = nlogn = O(nlogn) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 43 Useful Facts about Big-O (1/2) Big O, as a relation, is transitive: f  O(g)  g  O(h)  f  O(h) Sums of functions: If g  O(f) and h  O(f), then g+h  O(f).  c>0, O(cf)=O(f+c)=O(f  c)=O(f) E.g., O(2x 2 ) = O(x 2 +2) = O(x 2 -3) = O(x 2 ) If f 1 =O(g 1 ) and f 2 = O(g 2 ), then f 1 +f 2 = O(max(g 1,g 2 )) E.g., if f 1 (x) = x 2 = O(x 2 ), f 2 (x) = x 3 = O(x 3 ), then (f1+f2)(x) = x 2 + x 3 = O(x 3 ) = O(max(x 2, x 3 )) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 44 Useful Facts about Big-O (2/2) f 1 =O(g 1 ) and f 2 = O(g 2 ), then f 1 f 2 = O(g 1 g 2 ) E.g., if f 1 (x) = x 2 = O(x 2 ), f 2 (x) = x 3 = O(x 3 ), then (f1f2)(x) = x 2 ∙x 3 = x 5 = O(x 5 ) = O(x 2 ∙x 3 )) Other useful facts…  f,g & constants a,b  R, with b  0, -af = O(f)(e.g. 3x 2 = O(x 2 )) -f+O(f) = O(f)(e.g. x 2 +x = O(x 2 )) Also, the followings hold ( 그냥 참고하세요 ): -|f| 1-b = O(f);(e.g. x  1 = O(x)) -(log b |f|) a = O(f)(e.g. log x = O(x)) -g=O(fg)(e.g. x = O(x log x)) -fg  O(g)(e.g. x log x  O(x)) -a=O(f)(e.g. 3 = O(x)) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 45 Definition:  (g), exactly order g If f  O(g) and g  O(f) then we say “g and f are of the same order” or “f is (exactly) order g” and write f  (g). (f(x)=O(g(x)) 이고 g(x)=O(f(x)) 이면, f(x)=  (g(x)) 이며 g(x)=  (f(x)) 이다.) Another equivalent definition:  (g)  {f:R  R |  c 1 c 2 k  x>k: |c 1 g(x)|  |f(x)|  |c 2 g(x)| } (c 1 g(x)  f(x)  c 2 g(x) 를 만족하는 c 1 과 c 2 가 존재하면 f(x)=  (g(x)) 이다.) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 46 Rules for  Mostly like rules for O( ), except:  f,g>0 & constants a,b  R, with b>0, af   (f), but  Same as with O. f   (fg) unless g=  (1)  Unlike O. |f| 1-b   (f), and  Unlike with O. ( 참고 ) (log b |f|) c   (f).  Unlike with O. ( 참고 ) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 47 Examples of  (1/2) f(n) = … + n =  ( n 2 )? f(n)= … + n  n + n + n + … + n = n 2 f(n)= … + n = (n∙(n + 1))/2 = n 2 /2 + n/2  n 2 /2 n 2 /2  f(n)  n 2, i.e., c 1 = ½, c 2 = 1  f(n) =  ( n 2 ) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 48 Examples of  (2/2) f(y) = 3y 2 + 8ylogy =  (y 2 )? f(n)= 3y 2 + 8ylogy  11y 2 (if y > 1)(since 8ylogy  8y 2 ) f(n)= 3y 2 + 8ylogy  y 2 (if y > 1) y 2  f(y)  11y 2, i.e., c 1 = 1, c 2 = 11  f(y) =  ( y 2 ) Growth of Functions

Discrete Mathematics by Yang-Sae Moon Page 49 강의 내용 알고리즘 (Algorithms) 함수의 증가 (Growth of Functions) 알고리즘 복잡도 (Algorithm Complexity) Algorithms and Complexity

Discrete Mathematics by Yang-Sae Moon Page 50 What is Algorithm Complexity? The algorithmic complexity of a computation is some measure of how difficult it is to perform the computation. ( 문제 계산 (computation) 이 얼마나 어려운가를 나타내는 측정치이다.) Measures some aspect of cost of computation (in a general sense of cost). ( 계산을 위한 비용에 대한 측정치이다.) Common complexity measures: Time complexity: # of operations or steps required Space complexity: # of memory bits required Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 51 Complexity Depends on Input Most algorithms have different complexities for inputs of different sizes. (E.g. searching a long list takes more time than searching a short one.) ( 대부분의 알고리즘은 입력의 크기에 따라 복잡도가 달라진다. 당연 !) Therefore, complexity is usually expressed as a function of input length. ( 따라서, 복잡도는 입력의 크기 / 길이에 대한 함수로 표현한다.) This function usually gives the complexity for the worst- case input of any given length. ( 복잡도를 나타내는 함수는 통상 입력 크기가 최악인 경우를 고려한다.) Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 52 Example: Max Algorithm Problem: Find the exact order of growth (  ) of the worst- case time complexity of the max algorithm. Assume that each line of code takes some constant time every time it is executed. procedure max(a 1, a 2, …, a n : integers) v := a 1 {largest element so far} for i := 2 to n {go thru rest of elems} if a i > v then v := a i {found bigger?} {at this point v’s value is the same as the largest integer in the list} return v Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 53 Complexity Analysis of Max Algorithm (1/2) What’s an expression for the exact total worst-case time? (Not its order of growth.) ( 최악의 경우, 정확한 수행 시간을 어떻게 될까 ?) procedure max(a 1, a 2, …, a n : integers) v := a 1 t 1 for i := 2 to nt 2 if a i > v then v := a i t 3 return vt 4 Times for each execution of each line. ( 각 line 을 하나의 수행으로 볼 때의 시간 ) Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 54 Complexity Analysis of Max Algorithm (2/2) Worst case execution time: procedure max(a 1, a 2, …, a n : integers) v := a 1 t 1 for i := 2 to nt 2 if a i > v then v := a i t 3 return vt 4 Times for each execution of each line. ( 각 line 을 하나의 수행으로 볼 때의 시간 ) Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 55 Example: Linear Search procedure linear search x: integer, a 1, a 2, …, a n : distinct integers) i := 1t 1 while (i  n  x  a i )t 2 i := i + 1t 3 if i  n then location := it 4 else location := 0t 5 return locationt 6 Worst case: Best case: Average case (if item is present): Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 56 Example: Binary Search procedure binary search (x:integer, a 1, a 2, …, a n : distinct integers) i := 1 j := n while i a m then i := m+1 else j := m end if x = a i then location := i else location := 0 return location  (1) Key Question: How Many Loop Iterations? Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 57 Binary Search Analysis Suppose n=2 k. Original range from i=1 to j=n contains n elements. Each iteration: Size j  i+1 of range is cut in half. ( 매번 검색 범위 (j-i+1) 의 절반 (½) 씩 줄여 나간다.) Loop terminates when size of range is 1=2 0 (i=j). ( 검색 범위의 변화 : 2 k  2 k-1  2 k-2  …  2 1  2 0, 결국 반복 횟수 = k) Therefore, number of iterations is k = log 2 n =  (log 2 n)=  (log n) ( 반복 횟수 = k 이고, log 2 n = log 2 2 k 이므로 …) Even for n  2 k (not an integral power of 2), time complexity is still  (log 2 n) =  (log n). Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 58 Example: Bubble Sort nd pass1 st pass 3 rd pass4 th pass Consider # of compare operations only! (n-1) + (n-2) + … = ((n-1)n)/2 =  (n 2 ) Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 59 Example: Insertion Sort Also, consider # of compare operations only! … + (n-2) + (n-1) = ((n-1)n)/2 =  (n 2 ) Then, are all sorting algorithm’s complexities  (n 2 )? NO! …, merge sort, heap sort, quick sort, … Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 60 Names for Some Orders of Growth  (1)Constant  (log n)Logarithmic  (n)Linear  (n log n)Polylogarithmic  (n c )Polynomial  (c n ), c>1Exponential  (n!)Factorial Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 61 Tractable versus Intractable A problem or algorithm with at most polynomial time complexity is considered tractable (or feasible). P is the set of all tractable problems. (Polynomial 복잡도를 가지면, 풀만한 ( 풀기 쉬운 ) 문제라 여기며, 이러한 문제들 의 집합을 P 라 나타낸다.) A problem or algorithm that has more than polynomial complexity is considered intractable (or infeasible). (Polynomial 복잡도 이상이면 풀기 어려운 문제라 여긴다.) But, note that n 1,000,000 is technically tractable, but really impossible. c log log log n is technically intractable, but easy. Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 62 Unsolvable Problems Alan Turing discovered in the 1930’s that there are problems unsolvable by any algorithm. ( 튜링은 “ 어떠한 알고리즘으로도 풀 수 없는 문제가 있음 ” 을 밝혔다.) Example: the halting problem. Given an arbitrary algorithm and its input, will that algorithm eventually halt, or will it continue forever in an “infinite loop?” ( 주어진 알고리즘이 결국 정지하는지의 여부를 판단하는 문제는 결국 풀 수가 없다.) Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 63 P versus NP (1/3) P is the set of all tractable problems. (i.e., the problems have at most polynomial time complexity.) ( 통상적으로 polynomial complexity 를 가지면 P 이다.) NP is the set of problems for which there exists a tractable algorithm for checking solutions to see if they are correct. In other words, NP is the set of decision problems for which a given proposed solution for a given input can be checked quickly (in polynomial time) to see if it really is a solution. 주어진 입력에 대해 제시된 솔루션이 바른 해인지의 여부를 빠르게 (poly- nomial time) 판단할 수 있는 알고리즘이 존재하는 문제들의 집합이 NP 이다. 통상적으로 exponential/factorial complexity 를 가지면 NP 이다. Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 64 P versus NP (2/3) - skip NP-complete is the term used to describe decision problems that are the hardest ones in NP in the sense that, if there were a polynomial- bounded algorithm for an NP complete problem, then there would be a polynomial-bounded algorithm for each problem in NP. NP 중에서도 어려운 문제들이란 용어를 의미하며, 하나의 NP-complete 문제가 풀리면 (P 가 되면 ), 관련된 수많은 모든 NP-complete 문제가 동시에 풀리게 된다. 많은 학자들은 어려운 많은 문제들에 대해서 NP-complete 임을 증명 ( 특정 문제가 다른 NP-complete 문제로 해석 ( 변경 ) 될 수 있음을 보임 ) 하였다. Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 65 P versus NP (3/3) - skip We know P  NP, but the most famous unproven conjecture in computer science is that this inclusion is proper (i.e., that P  NP rather than P=NP). Whoever first proves it will be famous! Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 66 Computer Time Examples Assume time = 1 ns (10  9 second) per operation #ops(n)n=10n=10 6 log 2 n3.3 ns19.9 ns n10 ns1 ms n log 2 n33 ns19.9 ms n2n2 100 ns16 m 40 s 2n2n  s ,004.5 Gyr n!n!3.63 msOuch! You should carefully design algorithms and write programs! Algorithm Complexity

Discrete Mathematics by Yang-Sae Moon Page 67 강의 내용 알고리즘 (Algorithms) 함수의 증가 (Growth of Functions) 알고리즘 복잡도 (Algorithm Complexity) Algorithms and Complexity

Discrete Mathematics by Yang-Sae Moon Page 68 Homework #3 Algorithms and Complexity Homework #3 & Programming Assignment #1