西安电子科技大学：《算法设计技术 Algorithms Design Techniques》课程教学资源（PPT课件讲稿）Chapter 01 Basic Concepts in Algorithmic Analysis（主讲：刘静）

Textbook M.H.Alsuwaiyel,Algorithms design techniques and Analysis,Publishing House of Electronics Industry M.H.Alsuwaiyel著，吴伟昶，方世昌等译，算法设计 技巧与分析，电子工业出版社

Textbook ◼ M. H. Alsuwaiyel, Algorithms design techniques and Analysis, Publishing House of Electronics Industry ◼ M. H. Alsuwaiyel著，吴伟昶，方世昌等译，算法设计 技巧与分析，电子工业出版社

What's Algorithms? An algorithm is a procedure that consists of a finite set of instructions which,given an input from some set of possible inputs,enables us to obtain an output if such an output exists or else obtain nothing at all if there is no output for that particular input through a systematic execution of the instructions

What’s Algorithms? ◼ An algorithm is a procedure that consists of a finite set of instructions which, given an input from some set of possible inputs, enables us to obtain an output if such an output exists or else obtain nothing at all if there is no output for that particular input through a systematic execution of the instructions

Inputs Outputs (Problems) Instructions (Answers) Computers

Instructions Inputs (Problems) Outputs (Answers) Computers

Programming Data Algorithms Software Languages Structure Systems

Programming Languages Data Structure Algorithms Software Systems

Content Chapter 1 Basic Concepts in Algorithmic Analysis Chapter 5 Induction Chapter 6 Divide and Conquer Chapter 7 Dynamic Programming ■ Chapter 8 The Greedy Approach ■ Chapter 9 Graph Traversal Chapter 13 Backtracking Chapter 14 Randomized Algorithms ■ Chapter 15 Approximation Algorithms ■ Chapter 16 Network Flow Chapter 17 Matching

Content ◼ Chapter 1 Basic Concepts in Algorithmic Analysis ◼ Chapter 5 Induction ◼ Chapter 6 Divide and Conquer ◼ Chapter 7 Dynamic Programming ◼ Chapter 8 The Greedy Approach ◼ Chapter 9 Graph Traversal ◼ Chapter 13 Backtracking ◼ Chapter 14 Randomized Algorithms ◼ Chapter 15 Approximation Algorithms ◼ Chapter 16 Network Flow ◼ Chapter 17 Matching

Binary Search Let A[1...n]be a sequence of n elements.Consider the problem of determining whether a given element xis in A

Binary Search ◼ Let A[1…n] be a sequence of n elements. Consider the problem of determining whether a given element x is in A

Binary Search Example: A[1..14]=1457891012152223273235 X=22 Does X exist in A?How many comparisons do you need to give the answer?

Binary Search Example: A[1…14]=1 4 5 7 8 9 10 12 15 22 23 27 32 35 x=22 Does X exist in A? How many comparisons do you need to give the answer?

Binary Search Inputs:(1)An array A[1...n]of n elements sorted in nondecreasing order;(2)x, Output:jif x=A],and 0 otherwise; 1.lowk-1;high-n;衣-0； ■ 2.while (low<high)and (0) ■ 3. midk(low+high)/2; ■ 4. if x=A[mid]then mid; 5. else if x<A[mid]then highmid-1; ■ 6. else low-mid+1; 7.end while; 8.return

Binary Search ◼ Inputs: (1) An array A[1…n] of n elements sorted in nondecreasing order; (2) x; ◼ Output: j if x=A[j], and 0 otherwise; ◼ 1. low1; highn; j0; ◼ 2. while (lowhigh) and (j=0) ◼ 3. mid(low+high)/2; ◼ 4. if x=A[mid] then jmid; ◼ 5. else if x<A[mid] then highmid–1; ◼ 6. else lowmid+1; ◼ 7. end while; ◼ 8. return j;

Binary Search What's the performance of the algorithm Binary Search on a sorted array of size n? What's the minimum number of comparisons we need and in which case it will happen? v What's the maximum number of comparisons we need and in which case it will happen?

Binary Search ◼ What’s the performance of the algorithm Binary Search on a sorted array of size n? ✓ What’s the minimum number of comparisons we need and in which case it will happen? ✓ What’s the maximum number of comparisons we need and in which case it will happen?

Binary Search The number of comparisons performed by the algorithm Binary Search on a sorted array of size n is at most Llog n+1

Binary Search ◼ The number of comparisons performed by the algorithm Binary Search on a sorted array of size n is at most log n+1