CS计算机代考程序代写 algorithm Introduction

Introduction

Computational Problem Solving
Problems
Designing solution strategies
Developing algorithms (iterative and recursive)
Writing algorithms that implement the strategies
Understand existing algorithms and modify/reuse
Understanding an algorithm by simulating its operation on an input
Checking/proving correctness
Analyzing and comparing performance: complexity or efficiency
Theoretically: Using a variety of mathematical tools
Empirically: Code, run and collect performance data
Choosing the best

1

Complexity Analysis of Recursive Algorithms
Chapter 4: OMIT 4.2 & 4.6
Keep up with the reading assignments!

3

Why can’t we use the complexity calculation technique that we have been discussing for non-recursive algorithms?
4

5
Because of recursion!
Fibonacci numbers: F0 = 1; F1 = 1; Fn = Fn-1+Fn-2

Fib (n: non-negative integer)
1 if n=0 or 1 then return 1
2 else return Fib(n-1)+Fib(n-2)

So what do we do?

Develop a pair of equations (called “recurrences” or “recurrence relations”) that characterize the behavior of a recursive algorithms and
Solve those to obtain the algorithm’s complexity.
6

Recurrences
What are these?

A pair of equations giving T(n) of recursive algorithms in terms of the
cost of recursive calls
and the cost of other steps

Step 1: Develop Recurrence Relations
How?
Determine what the base case(cases) is (are).
Determine steps that will be executed when the input size matches the base case(s).
Calculate the complexity of those steps.
Write the first part of the RR as T(base case input sizes) = what you calculated
8

Step 1: Develop Recurrence Relations
How?
Determine steps that will be executed when the input size is n, different from the base case(s).
Determine how many recursive calls (and with what input size in relation to the original input size of n) will be made.
Calculate the complexity of all other steps, excluding the recursive calls.
Write the second part of the RR as T(n) = T(input size for first recursive call) + T(input size for next recursive call) +…+complexity of all other steps.
9

10
Recursive algorithm example
T(n)= 4 = Θ(1) when n < 2 T(n)=T(n-1)+T(n-2)+7 =T(n-1)+T(n-2)+ Θ(1) when n≥2 Fib (n: non-negative integer) 1 if n=0 or 1 then return 1 2 else return Fib(n-1)+Fib(n-2) 11 Divide & Conquer Algorithm A recursive algorithm that divides the input each time into non-overlapping parts & apply itself to these smaller inputs until the base case is reached, and then recursively combines the subproblem solutions to obtain a solution to the overall problem Example: Merge Sort Divide & Conquer Algorithm Find-Max-Recursive(A:array[i…j] of numbers) if i=j then return A[i] else mid=floor((i+j)/2) return max(Find-Max-Recursive(A[i…mid), Find-Max-Recursive(A[mid+1…j]) Thinking Assignments understand this algorithm is it correct? can you prove it? how? can you draw a recursion tree for A=[1,0,-5,7,23]? develop its recurrences 12 13 General form of divide-and-conquer algorithm recurrences           D & C Algorithms Recursion tree method can be used to solve these kinds of recurrences, like we did for Merge Sort 14 Reading Assignment Section 4.1 understand the maximum subarray problem understand the divide and conquer solution understand FIND-MAX-CROSSING-SUBARRAY simulate it on some specific arrays using paper and pen understand FIND-MAXIMUM-SUBARRAY draw the recursion tree for some specific arrays understand its recurrences (equations 4.7) Thinking Assignment: do exercise 4.1-1 come to next class with questions/confusions other than answering your questions, this section will not be discussed in class 15 Solving Recurrences Recursion-tree method (4.4) Substitution method (4.3: omit “changing variables”) Master method (4.5) Backward substitution method (not in text) Forward substitution method (not in text) Reading Assignments: 4.3, 4.4, 4.5 16 Recurrence relations of Merge Sort 17 18 Analysis of Merge Sort 19 Suppose a divide-and-conquer algorithm has these recurrences           Another Example 20 Recursion-tree method 21 22 23 The cost of the entire tree Alternate solution using finite summation result 24 25 The substitution method The substitution method for solving recurrence entails two steps: 1. Guess the form of the solution. 2. Use mathematical induction to find the constants and show that the solution works. 3. If the inductive step of the proof fails, your guess is probably wrong. 26 How do you guess? (1) If a recurrence is similar to one you have seen, guess a similar solution. (2) Draw the recursion tree to get an approximate idea of what the solution might be. (3) Trial and error. 27 Example of (1) Guess Now show using induction: 28   Base case   However, Click to edit Master text styles Second level Third level Fourth level Fifth level 29 Now Assume We have to show 30 Guess a solution using the recursion tree method approximately Then prove that it is correct Example of (2) 31 32   We need to prove by induction that Base case   Click to edit Master text styles Second level Third level Fourth level Fifth level 33 Now Assume We have to show 34 Subtleties Example of (3): Trial and error: correct guess; fixable problem with proof Guess Show Base Case: Assume Inductive Step: proof fails   35  Instead, show Base case: Assume Then This technique can be used if the inductive step fails due to a constant additive or subtractive term 36 Example of (3): Trial and error (wrong guess) Avoiding pitfalls Guess Works for the base case: T(1)=1 ≤ c*1when c≥1 Show Assume   You cannot find such a positive constant. This is an example of inductive proof failure suggesting that your guess is WRONG 37 Another example (for you to read and understand) T(n)=3T(n/4) + cn2, T(1) = c Guess T(n)=O(n2) We want to show that T(n) ≤ dn2 for some constant d > 0. Works for the base case (why?) . So assume T(n/4) ≤ d(n/4)2

38
Changing variables method
omit

To deal with recursive call input sizes that are square roots, cube roots and powers of n less than 1

39
The master method
No need to memorize
Learn how to apply

The Master Theorem
If T(n)=aT(n/b) + f(n) (and T(base case)=some constant) and a and b are constants, then:
40

41

42

43

44

45
When master method doesn’t apply
omit
The master method does not apply to the recurrence
even though it has the proper form: a = 2, b=2, f(n)= n lgn, and
It might seem that case 3 should apply, since f(n)= nlgn is asymptotically larger than
The problem is that it is NOT polynomially larger, i.e., not larger by a term nε.

46
Method of backward substitutions

Start with the recurrence relation for T(n), and
repeatedly expand its right hand side by substituting for the T terms.
After several such expansions, look for and find a pattern that allows you to express T(n) as a closed-form formula.
If such a formula is evident, check its validity by direct substitution into the recurrence relations.

47
T(n)=T(n-1)+n; T(0)=1

T(n-1)=T(n-2)+(n-1)
So T(n)=T(n-2)+n+(n-1)

T(n-2)=T(n-3)+(n-2)
So T(n)=T(n-3)+n+(n-1) +(n-2)

T(n-3)=T(n-4)+(n-3)
So T(n)=T(n-4)+n+(n-1) +(n-2)+(n-3)

Eventually, T(n)=T(n-n)+n+(n-1) +(n-2)+(n-3)+
…+(n-(n-1))=T(0)+n+(n-1)+(n-2)+(n-3)+…+1= 1+ n(n+1)/2

Check:
LHS of recurrence T(n) = 1+ n(n+1)/2 = n2/2+n/2+1
RHS = T(n-1) + n = 1+ (n-1)n/2 + n = n2/2+n/2+1

48
Method of forward substitutions

Start with the recurrence relation for T(base case), and repeatedly calculate non-base cases, e.g., T(1), T(2) etc. After several such calculations, look for and find a pattern that allows you to express T(n) as a closed-form formula. If such a formula is evident, check its validity by direct substitution into the recurrence relations.

49
T(n)=T(n-1)+1; T(0)=1

T(1)=T(0)+1=1+1=2
T(2)=T(1)+1=2+1=3
T(3)=T(2)+1=3+1=4
T(4)=T(3)+1=4+1=5
T(5)=T(4)+1=5+1=6

T(n)=n+1

Check:
LHS = T(n) = n+1
RHS = T(n-1)+1 = n+1

50
Complexity of Recursive Algorithms
First develop the recurrences from the algorithm
Then solve them using the most appropriate method

How do you know which method to apply?
Substitution method: generally applicable

Recursion tree method and Master method: for Divide and Conquer algorithms that reduce inputs by a fixed factor

Backward/Forward substitution method: for algorithms that reduce input by a constant amount

51

Summary
We have discussed several tools and techniques for mathematically determining the complexity of algorithms:
For non-recursive algorithms, calculate T(n) by adding up the (cost * # of executions) of each step
For recursive algorithms, develop the recurrence relations and solve them using a variety of techniques to obtain T(n)
Once you obtain an exact expression for T(n) [or through various approximations an upper or lower bound for T(n)] as a function of n, then you can determine the order of complexity of the algorithm.

52

Empirical Complexity
Another approach is to determine T(n) by plotting it as a graph of actual time taken by the algorithm versus input size by:
Coding the algorithm in a programming language
Randomly generating inputs of different sizes: typically from small sizes up to 100K’s or millions
Running the program on each of these inputs and measuring the time taken using the system clock
Plotting time against input size
Determining the appropriate g(n) that fits this graph or provides an upper or lower bound (see next slide for examples of g(n))
This function g will then give you the order of complexity of the algorithm
53

54

1 1 1 1 1 1 1 1 1 1 loglogn 0 0.66444870745389994 1 1.2153232957367781 1.37014335194601 1.489211469238126 1.5849625007211561 1.6644487074538901 1.732020845644618 1.7905350238931339 logn 1 1.5849625007211561 2 2.3219280948873622 2.5849625007211601 2.8073549220576042 3 3.169925001442337 3.3219280948873631 3.4594316186372982 n 2 3 4 5 6 7 8 9 10 11 nlogn 2 4.7548875021634647 8 11.60964047443681 15.50977500432694 19.651484454403231 24 28.529325012980809 33.219280948873632 38.053747805009998 n-squared 4 9 16 25 36 49 64 81 100 121

î
í
ì
+
£
Q
=
otherwise
n
f
b
n
aT
c
n
if
n
T
)
(
)
/
(
)
1
(
)
(

î
í
ì
>
+
=
=
1
)
2
/
(
2
1
)
(
n
if
cn
n
T
n
if
c
n
T

T
n
if
n
T
n
n
if
n
(
)
(
)
(
/
)
(
)
=
=
+
>
ì
í
î
Q
Q
1
1
2
2
1

)
log
(
log
)
(
n
n
cn
n
cn
n
T
Q
=
+
=

ë
û
î
í
ì
Q
+
=
Q
=
otherwise
n
n
T
n
if
n
T
)
(
)
4
/
(
3
1
)
1
(
)
(
2

ë
û
î
í
ì
+
=
=
otherwise
cn
n
T
n
if
c
n
T
2
)
4
/
(
3
1
)
(

(
)
(
)
(
)
)
(
)
(
,
)
(
.
.
)
(
13
16
)
16
/
3
(
1
1
16
3
16
3
)
(
2
3
log
2
3
log
2
3
log
2
0
1
log
0
3
log
2
4
4
4
4
4
n
o
n
T
so
polynomial
quadratic
a
n
T
e
I
n
cn
n
cn
n
cn
n
cn
n
T
i
i
n
i
i
=
< Q + = Q + - = Q + ÷ ø ö ç è æ < Q + ÷ ø ö ç è æ = å å ¥ = - = ë û T n T n n T ( ) ( / ) ( ) = + = ì í î 2 2 1 1 ) log ( ) ( n n O n T = n cn n T log ) ( £ ? 0 1 log 1 ) 1 ( 1 = £ = c T ) 2 if ( 2 2 log 2 ) 2 ( 4 ³ = £ = c c c T ë û ë û ë û T n c n n ( / ) / log / 2 2 2 £ ë û ë û ) 1 (if log ) 1 ( log 2 log log 2 log ) 2 / log 2 / ( 2 ) ( . c n cn c n n cn n cn n cn n n cn n n n c n T ³ £ - - = + - = + £ + £ 2 ) 2 ( = T cn n T n T n T + + = ) 3 / 2 ( ) 3 / ( ) ( ) 1 if ( 2 2 log 2 ) 2 ( 2 ³ = £ = d d d T n dn n T log ) ( £ ) 3 / log( ) 3 / ( ) 3 / ( n n d n T £ ) 3 2 3 /(lg 0 ) ) 3 2 3 (lg ( lg ) ) 3 2 3 (lg ( lg ) 2 3 lg 3 2 3 lg 3 1 ( lg )) 2 / 3 lg( (lg 3 2 ) 3 lg (lg 3 ) ( - >
>


£



=
+
+

=
+

+

£
c
d
or
cn
dn
when
n
dn
cn
dn
n
dn
cn
dn
n
dn
cn
n
dn
n
dn
n
T

)
3
/
2
log(
)
3
/
2
(
)
3
/
2
(
n
n
d
n
T
£

ë
û
é
ù
1
)
1
(
;
1
)
2
/
(
)
2
/
(
)
(
=
+
+
=
T
n
T
n
T
n
T

)
(
)
(
n
O
n
T
=

2
/
)
2
/
(
cn
n
T
£

cn
cn
cn
cn
n
T
£
/
+
£
+
+
£
1
1
2
/
2
/
)
(

cn
n
T
£
)
(

1
1
*
1
)
1
(
least
at
is
c
when
c
T
£
=

ë
û
é
ù
T
n
T
n
T
n
(
)
(
/
)
(
/
)
=
+
+
2
2
1

1
)
(
)
(
)
(

£
Þ
=
cn
n
T
n
O
n
T

1
)
(
1
)
1
2
/
(
)
1
2
/
(
)
(

£
+

+

£
cn
n
T
cn
cn
n
T

1
2
/
)
2
/
(

£
cn
n
T

2
)
1
(
1
)
1
(
least
at
is
c
when
holds
c
T

£
=

ë
û
T
n
T
n
n
T
(
)
(
/
)
(
)
=
+
=
ì
í
î
2
2
1
1

)
(
)
(
n
O
n
T
=

T
n
cn
(
)
£

??
)
1
(
)
2
/
(
2
)
(
cn
c
n
n
cn
n
cn
n
T
£
+
=
+
£
+
£

2
/
)
2
/
(
cn
n
T
£

ë
û
ë
û
d
c
or
d
c
d
when
dn
   
c
d
n
   
cn
dn
   
cn
n
d
   
cn
n
d
   
cn
n
T
 
n
T
£
£
+
£
+
=
+
=
+
£
+
£
+
=
13
16
,
)
16
3
(
,
)
16
3
(
16
3
)
4
/
(
3
4
/
3
)
4
/
(
3
)
(
2
2
2
2
2
2
2
2
2

Tn T n n() ( )lg 2

Let
m nlg
.
T T m
m m
( ) ( )
/
2 2 2
2
 

Let
)2()(
m
TmS

)2/()2(
2/
mST
m

Then
Sm Sm m() (/) 2 2
.
 
   

Sm Om m
Tn T Sm Om m
O n n
m
() (lg )
() ( ) () (lg )
(lg lglg)
2

)
2
(
)
(
m
T
m
S
=

)
2
/
(
)
2
(
2
/
m
S
T
m
=

Let

.

Let

Then

.

_925211299.unknown

_925211400.unknown

_1232437688.unknown

_1232437773.unknown

_925211449.unknown

_925211331.unknown

_925211262.unknown

)
log
(
)
(
0
)
(log
(
)
(
:
1
)
n
n
a
a
b
b
n
T
then
for
O
n
f
if
Q
=
>
=

e
e

))
(
(
)
(
1
tan
)
(
)
/
(
0
)
(log
(
)
(
:
3
)
n
f
n
T
then
c
t
cons
some
for
n
cf
b
n
af
if
and
for
n
f
if
n
a
b
Q
=
< £ >
W
=
+
e
e

)
lg
log
(
)
(
)
log
(
)
(
:
2
n
n
T
then
n
f
if
n
n
a
a
b
b
Q
=
Q
=


Tn Tn n() (/) 9 3

a b fn n
n n fn On
  
 

9 3
3 3
9
2
91
, ,()
, () ( )
log log

Case Tn n1
2
 () ( )


Tn T n() ( /) 2 3 1

a b fn
n n fn
  
 
1, 32 1
1
32
1
0
/,()
(),
log
/

Case Tn n2 () (log )

·

·

_925234096.unknown

_925234284.unknown

_925234285.unknown

_925234286.unknown

_925234229.unknown

_925234054.unknown


Tn Tn n n() (/) log 3 4

)()(,
log)(,4,3
3log
793.0
3log
44



nnfnn
nnnfba

Case
af(n/b)= (
n
) (
n
)
n
n=cf(n)
c= n
Tn n n
3
3
4 4
3
4
3
4
Check
for and suffi ciently la rge
log log
,
() (log )

 

)
(
)
(
,
log
)
(
,
4
,
3
3
log
793
.
0
3
log
4
4
e
+
W
=
=
=
=
=
n
n
f
n
n
n
n
n
f
b
a

·

_925234530.unknown

_1231838525.unknown

_925234480.unknown

,
lg
)
2
/
(
2
)
(
n
n
n
T
n
T
+
=

.
log
n
n
a
b
=

.
log
n
n
a
b
=

/docProps/thumbnail.jpeg