Notes-ch1-07

SHEN’s CLASS NOTES

Chapter 1 Introduction

1.1 Algorithms and problems

An algorithm

is a well-defined computational procedure to solve a computational problem (or problem for short).

An algorithm must be correct. A good algorithm must be readable, time-efficient, space- efficient.

A problem

defines the requirements that valid output values must satisfy for a given set of input values.

Usually, we are only interested in those problems that allow infinitely many different sets and sizes of input values.

1

SHEN’s CLASS NOTES

For example, the sorting problem takes n numbers as input set and requires the n numbers be arranged in descending or ascending order as the valid output, where the n can be any positive integer.

For a particular set of input values, the problem is referred as an instance of the problem. Therefore, a problem must contain infinitely many instances.

Solving a problem

is to find a valid output for any given input, which is done by an algorithm.

1.2 Relationship between an algorithm and a data structure

A data structure

is a way to store and organize data in order to facilitate accesses and modifications.

2

SHEN’s CLASS NOTES

An efficient algorithm relies upon efficient data structure. No single data structure works well for all purposes. It is important to get familiar with commonly used data structures that will be overviewed in Chapters 10-14.

1.3 Relationship between an algorithm and a program

A program

is a piece of code written in a particular language such as Pascal, C, C++, Java, or even some assembly language.

Therefore, programs are language dependent or even machine dependent. A program can often be viewed as a detailed implementation of an algorithm with some limitations such as memory capacity, the largest number allowed, the largest size of an array, etc.

3

SHEN’s CLASS NOTES

An algorithm is of more abstract notion. It is language independent, machine independent. An algorithm is well defined as far as its steps can clearly implemented by any known language.

Algorithms and programs are very closed related. We often use a known real language such as Pascal, C, C++ to describe an algorithm. Then, the algorithm looks like a program. However, in such a program, the grammar of the language will not be strictly followed and some notations may be changed to make the algorithm more readable. Such a language is called a pseudo language.

Example 1.

Problem: sorting n numbers Input:

A[1], A[2], …, A[n]

Output: arrange the n numbers such that

A[1] ? A[2] ? …? A[n].

4

SHEN’s CLASS NOTES

Algorithm Selection Sort (A[1..n]); 1 2 3 4 5 6 7

for (i = 1, i ? n, i++) End

do { key = i

for (j = i, j ? n, j++)

do if A[j] < A[key]

then key ? j

A[i] ? A[key]

We could call the language used in example 1 pseudo C++. However, this is not important to identify which language it looks like. We accept the presentation of an algorithm as far as its steps are clearly implementable. Example 2 shows another way to present the same sorting algorithm of Example 1.

Example 2.

5

SHEN’s CLASS NOTES

Algorithm Selection Sort (A[1..n]);

1 for (i = 1, i ? n, i++) 2 3 4 5 6 End

By allowing this kind of abstraction, we can concentrate on design methodology and pay less effort to the implementation details.

If an algorithm is implemented by a program with a particular language, you may call such program an algorithm also. However, sometimes, a piece of program solves only a particular instance of a problem or several instances of a problem. For example, a program may be written to compute the average temperature from the data collected from fixed 10 locations. We can hardly call them an algorithm.

do { find j such that

}

A[j]= Min{A[i], A[i+1], …, A[n]}; A[i] ? A[j]

6

SHEN’s CLASS NOTES

1.4 Performance of an algorithm

An algorithm must be correct, highly readable, and efficient. By efficient, we mean that the algorithm must use as little memory space as possible and use as little time as possible. The memory space needed and the time used are called space complexity and time complexity, respectively. Normally, the two complexities are related to the input size. For example, sorting 10,000 numbers will take much larger space and longer time than that of sorting 100 numbers. Also, large numbers may take longer time to process than small numbers. Therefore, the space or time complexity is represented by a function that reflects the relationship between the space or time required by the algorithm and the input size. We need some assumptions on the input size.

The models of input size

There are two commonly used models.

7

SHEN’s CLASS NOTES

(1) Use the number of numbers or number of set elements

as the input size. For example, if we are given n numbers to sort, then the input size is n. In this model, we assume one memory cell will hold a number no matter how big the number is. Moreover, we assume that an operation between any two numbers takes an equal constant time. For example, (5 + 7) will takes the same amount of time as that for (10225560 + 45787899909).

(2) The number of bits (or digits) that are used for

encoding the set of input values. This model uses the number of bits fed into a computer as the input size. This model is useful when a number is so large such that the assumption that any operation takes a constant time makes no sense. Moreover, the input may contains only one number or few numbers. For example, if we want to determine if a given number x is a prime number, the input size should not be considered to be one. We need infinitely many different input sizes! For the prime number problem,

8

SHEN’s CLASS NOTES

we use lgx to be the input size because lgx bits are used to encode the number x.

In most cases, we use model (1).

How to represent the time complexity and space complexity

The time complexity of an algorithm is represented by a function from the input size to the time required by the algorithm to produce corresponding result.

The space complexity is represented by a function from the input size to the total number of different memory cells required by the algorithm to produce the result. This book will focus on the time complexity.

Because different machines have different speeds, the same algorithm may need a different time to finish on different machines. In order to fairly judge the time efficiency of an algorithm, we count the number of basic operations executed by the algorithm and use this

9

SHEN’s CLASS NOTES

number to represent the time complexity of a given algorithm. This number will not change from one machine to another. Moreover, we also ignore the effect caused by different compilers. We count the number of operations in the pseudo source code.

Because counting exactly the number of operations is difficult and not necessary, we usually pay more attention to the asymptotic behavior of the time complexity when the input size n goes to infinity. In other words, we pay more attention to the order or rate the complexity function grows when n goes to infinity.

For example, given two functions, f(n) = 2n and g(n) = 9n, we would consider them to be in the same order.

However, if f(n) = 200n and g(n) = n2, then g(n) grows much faster than f(n) although f(n) may be larger than g(n) when n is not very large. We would say that f(n) has smaller and better time complexity.

10

SHEN’s CLASS NOTES

We wish to design an algorithm whose complexity has lower order.

The Growth of Functions (O, ?, ? notations)

We introduce some notations used to compare growth rate between two complexity functions. We assume all complexity functions have positive values.

Definition 1 Let f(n) and g(n) be two functions from the set of non-negative integers to the set of real numbers. We say that f(n) is O(g(n)) (often written as f(n) = O(g(n)) if there are positive constant c and n0 such that f(n) ≤ cg(n)

whenever n > n0.

Example 3.

n3 + 2n +5 = O(n3) (c = 10, n0 = 1), nlgn = O(n2)

(c = 1, n0 = 1).

11

SHEN’s CLASS NOTES

Definition 2 Let f(n) and g(n) be two functions from the set of non-negative integers to the set of real numbers. We say that f(n) is ?(g(n)) (often written as f(n) = ?(g(n)) if there are positive constant c and n0 such that f(n) ≥ cg(n) whenever n > n0. Example 4.

n3 + 2n +5 = ? (n3) (c = 1, n0 = 1), n2 = ? (nlgn) .

Definition 3 Let f(n) and g(n) be two functions from the set of non-negative integers to the set of real numbers. We say that f(n) is ?(g(n)) (often written as f(n) = ?(g(n)) if and only if f(n) = O(g(n)) and f(n) = ?(g(n)).

(c = 1, n0 = 1),

Example 5.

n3 + 2n +5 = ? (n3).

12

SHEN’s CLASS NOTES

Definition 4 Let f(n) and g(n) be two functions from the set of non-negative integers to the set of real numbers. We say that f(n) is ?(g(n)) (often written as f(n) = ?(g(n)) if for any positive number c > 0, there exists a constant n0 such that

Obviously, f(n) = ?(g(n)) means

f(n)lim?0. n??g(n)

f(n) ≤ cg(n) whenever n > n0.

Example 6. 200n = o(nlgn)

Definition 5 Let f(n) and g(n) be two functions from the set of non-negative integers to the set of real numbers. We say that f(n) is ?(g(n)) (often written as f(n) = ?(g(n)) if for any positive number c > 0, there exists a constant n0 such that f(n) ≥ cg(n) whenever n > n0.

13

SHEN’s CLASS NOTES

Obviously, f(n) = ?(g(n) means

n??

limf(n)g(n)??.

Note. ? - notation is very seldom used.

The following is a list of commonly used representative functions in the order of their growth-rates:

lglgn, lgn, n, nlglgn, nlgn, n(lgn)2, n2, n3, 2n, n!, nn.

How to analyze the complexity of an algorithm

As we have discussed earlier, we use the total number of operations used by an algorithm as the time complexity. If we consider the asymptotic complexity, we can further simplify our analysis. We only need to count the number times the major operation will be executed. The major operation is the one that is executed most often.

14

SHEN’s CLASS NOTES

Example 7.

Procedure Linear search (x, A[1..n]) Input:

number x and array A of n numbers

Output: index i if A[i] = x, 0 otherwise. 1 i ?1

2 while (i ≤ n and x ≠ A[i]) 3 5 6 7 End

The major operations in the procedure are the comparisons between x and elements of A. As we can see that the number of such comparisons is at most n. Therefore, the time complexity is T(n) = O(n).

do i ? i + 1 then return (i) else return (0)

4 if i ≤ n

15

SHEN’s CLASS NOTES

The reason behind this is that there are only a small constant number of different kinds of operations in any algorithm. The commonly used operations include additions, subtractions, multiplications, divisions, data movements, pointer settings, comparisons, and so on. The number of different operations used by an algorithm is a small constant. Suppose there are c different operations, O1, O2, …, Oc, where O1 is the major operation. Let Oj be executed nj times. 1 ≤ j ≤ c. Then the total number of operations = ?nj≤ c n1.

j?1c

Also, we assume different operations require an equal amount of time to finish. This assumption is valid from asymptotic point of view. (For example, the multiplication may needs 10 times more time than the addition, but the 10 is only a small constant.) Therefore, T(n) = O(n1).

16

SHEN’s CLASS NOTES

Note. A little care must be taken. The pseudo code may contain some operations that are not basic operations. For example, if the pseudo code contains an operation of or

We cannot consider any of them as a single operation because they represent a single step, not a single operation. Such a step itself needs many operations depending on the size of n. We need to analyze how many basic operations to implement them first, and then add to the total number of basic operations. The integer n itself is treated as a regular variable although it is arguable assumption when n ? ?.

x ? n!

z ? Min {A[1], A[2], …, A[n]}

1.5 The worst case, best case, and average case analysis

Look at the linear search algorithm. Given an array of n numbers and a number x, if x = A[1], then we are lucky and the algorithm will quickly produce the result. However, if x is not contained in this array, then the

17

SHEN’s CLASS NOTES

algorithm needs n comparisons, which represents the worst case.

Therefore, the worst case analysis is to get a upper bound on the number of operations the algorithm requires even in the most difficult case. For the linear search algorithm, it is O(n).

The best case analysis is to get an estimate on the minimum number of operations required by the algorithm in most lucky case. In the case of linear search, it is O(1).

The average case analysis is to get an estimate on the average number of operations the algorithm may require over all possible sets of input values. If we assume the x is contained in the array A and has an equal probability 1/n to be A[i], 1 ≤ i ≤ n, then the average complexity of the linear search is

(1 + 2 + … + n) / n = (n+1)/2 = O(n).

Usually, we need to know the distribution of all

possible sets of input values for the average analysis. The main focus of this book is on the worst case analysis.

18

SHEN’s CLASS NOTES

1.6 Recurrence Relations

In this section, we will not present a general discussion on recurrence relations. The general discussion can be found in many discrete mathematics books. We focus on a special form of recurrence relation:

T(n) = aT(n/b) + f(n) T(1) = ?(1)

where a and b are two constants.

We often derive to the above relation when we use divide-conquer method to solve a problem. We introduce several approaches to solving this relation.

The substitution method This method consists of two steps: 1. Guess a form of solution

2. Using mathematical induction to prove that this form is valid.

19

SHEN’s CLASS NOTES

Example 8.

Solve the following recurrence relation:

T(n) = 2T(?n/2?) + n.

Solution:

1. We guess T(n) = O(nlgn).

2. Assume T(n) ≤ c nlgn. This must be true for some c > 0 and n = 2.

Assuming this relation holds for T(k) when k ≤ (?n/2?), we have

T(n) = 2T(?n/2?) + n

≤ 2(c?n/2? lg (?n/2?)) + n ≤ 2(cn/2)lg (n/2) + n

≤ cnlg (n/2) + n ≤ cn(lg n -1) + n

Therefore, we can select a constant c such that T(n) ≤ cnlgn for all n > 1, which means that T(n) = O(nlgn).

= cn lgn –cn + n ≤ cn lgn

(if c ≥ 1)

20

SHEN’s CLASS NOTES

Note. We often use variable transformation before solving the relations.

Example 9.

T(n) = 2T(?n?) + lg n.

Setting n = 2k, the above relation becomes

T(2k) = 2T(2k/2) + k.

Let T(n) = S(k), we obtain S(k) = 2S(k/2) + k = ?(klgk).

Then, we have T(n) = ?(klgk) = ?(lg n lglg n).

The summation method and recursion-tree method

The summation method is demonstrated by the following example.

Example 10.

Solve T(n) = 2T(n/2) + nlgn.

21

SHEN’s CLASS NOTES

Solution:

Setting n = 2k, the above relation becomes T(2k) = 2T(2k-1) + k2k Letting W(k) = T(2k), we have W(k) = 2W(k-1) + k2k = 2[2W(k-2) + (k-1)2k-1] + k2k = 22W(k-2) + (k-1)2k + k2k

= 22[2W(k-3) + (k-2)2k-2] + (k-1)2k + k2k = 23W(k-3) + (k-2)2k + (k-1)2k + k2k = ……

= 2k-1W(1) + 2×2k + 3×2k + …+ (k-1)2k + k2k = 2k-1W(1) + 2k [2 + 3 + …+ (k-2) + (k-1) + k] = 2k-1W(1) + 2k [k(k+1)/2 -1] = ?(k22k) = ?(nlg2n).

22

SHEN’s CLASS NOTES

The summation steps can be illustrated by a recursion-tree as follows.

W(k) = 2W(k-1)+k2k

k2k

k2k

W(k-1) W(k-1) (k-1)2k-1

(k-1)2k-1

W(k-2) W(k-2) W(k-2) W(k-2)

(a)

(b)

k2k (c)

k2k

(k-2) recursions (k-1)2k-1

(k-1)2k-1 (k-1)2k (k-2)2k

(k-2)2k-2 (k-2)2k-2 (k-2)2k-2 (k-2)2k-2

W(1) W(1)

???????????(d)

W(1) W(1) ?(2k)

Fig. 1 The construction of recursion tree for W(k) = 2W(k-1) + k2k of Example 10, where (b) and (c) show the first two recursion steps.

23

SHEN’s CLASS NOTES

The Master method

The Master method directly gives the answer to the recurrence relation (1) if the function f(n) satisfies certain conditions.

Theorem 1 (Master Theorem)

Given a recurrence relation T(n) = aT(n/b) + f(n), where a ?1 and b > 0 are two positive constants, the asymptotic bound of T(n) can be obtained in the following cases:

1. If f(n) = O(nlgba??) for some ? > 0,

then T(n) = ?(nlgba). then T(n) = ?(nlgbalgn).

2. If f(n) = ?(nlgba),

3. If f(n) = ?(nlgba??) for some ? > 0, and if af(n/b) ≤ cf(n) for some c < 1 and all n > n0, then T(n) = ?(f(n)).

Proof. See the textbook. Omitted.

24

SHEN’s CLASS NOTES

Example 11

Obtain an asymptotic bound for the following recurrence relations using the master theorem.

(a) T(n) = 9T(n/3) + n (b) T(n) =T(2n/3) +1

(c) T(n) = 3T(n/4) + nlgn.

Solution:

(a) T(n) = 9T(n/3) + n

lgba = lg39 = 2. Set ? = 0.5.

We have f(n) = n = O(n2-0.5)= O(n1.5). Therefore,

T(n) = ? (n2). (b) T(n) =T(2n/3) +1

lgba = lg3/21 = 0.

Since n0 = 1, the first rule in the Master Theorem is not applicable, but second rule can be applied. Therefore,

T(n) = ? (n0lgn) = ? (lgn).

25

SHEN’s CLASS NOTES

(c) T(n) = 3T(n/4) + nlgn

lgba = lg43 = 0.793.

Obviously, the first two rules of the Master Theorem do not apply. We check the third rule. Setting ? = 0.1, we have

f(n) = nlgn = ?(n) = ?(n0.793?0.1). Moreover, we have

af(n/b) = 3(n/4)lg(n/4) ≤ (3/4)nlgn If we set c = 3/4, we will have,

for any n > 1. for any n > 1,

af(n/b) ≤ (3/4)nlgn = cf(n). Therefore, by the Master Theorem, T(n) = ?(nlgn).

1.7 The Complexity of Problems

We notice that some problems are easier to solve, some are harder, and some are very difficult or even not solvable. For a given problem we wish to know how hard the problem is. When we have designed an

26

SHEN’s CLASS NOTES

algorithm, we also wish to know if we can do better, or if we have reached the bottom. For example, it is well-known that any comparison-based sorting algorithm needs?at least lgn! comparisons to sort n numbers. Therefore, this result save researchers a lot of efforts and time to search for a better algorithm which will never be obtained. We define the Complexity of a problem to be the minimum time required to solve this problem.

Obtaining a complexity lower bound for a given problem is often an important topic. An algorithm is called optimal if its time complexity matches with the problem lower bound. But, before you can claim your algorithm is optimal you need to obtain its lower bound. We will discuss some techniques and results on this issue.

There are many difficult problems whose complexities are not known. For those problems, the best known algorithm needs an exponential time. A problem is called tractable if it can be solved in polynomial time, otherwise, intractable. Because the exponential function grows much faster than any polynomial function, we would like to draw a line between these two classes of functions. A problem that can be solved in polynomial time is said to belong to class P. There is a class of problems whose tractability is not known. What we know is that they can be solved by a non-deterministic computer in polynomial time. Problems that can be solved by a non-deterministic computer in polynomial time are said to belong to class NP. Class P is a subset of class NP. The NP-completeness theory has been

27

SHEN’s CLASS NOTES

developed to characterize those NP problems for witch no polynomial time algorithm is known so far. Moreover, if any of them can be solved some day in polynomial time, then all NP problems can be solved in polynomial time. Those problems are said to belong to NP-complete class. Obviously, if any NP-complete problem is proven to be not polynomial solvable, then all problems in NP-complete class are not polynomial solvable. We will discuss the NP-complete problems and how to prove a problem to be in this class in Chapter 34.

End of Ch. 1.

28

本文来源：https://www.bwwdw.com/article/zkcg.html