Solution Correctness a Using the merge algorithm we get the Is your solution correct? olution:{1,357,910.122145} erge algorithm ■ Any left problems? array in any case? a How to fulfill the condition m Using other method a Using the same divide and conquer method To a trivial state: for example there are only one element for sorting Complexity Analysis Notation e a How many memories does the algorithm use? a If there exists two positive constants c and d such a How many steps does the algorithm use? that when n tends to infinity we have cg(n)sf(n)< m Let T(n) be the number of steps used in the algorithm g(n) then we call g(n) is an asymptotically tigh an array of length n, then we know that by the divide and conquer that f(n)=e(g(n)) B T(n=2T(n/2)+en), where e is an asymptotic a Other notations ofnot tight upper bound o(upper expression means tighten bound, its definition will be bound] and Q lower bound], o[not tight lower bound the next page【我们假设每次均分,而且正好 can be found in p. 41 in the reference book. 可以均分】 Left problems Exercise a What is the upper bounds and lower bounds for the a Big integers expression, addition and orting problem? multiplication in a 32-bits microcomputer. a How to solve the recursive equality(or inequality)? (n)=2T(n2)+n) a How to express a big integer? a How to converge the above equality to a well posed a We use an n-length of array of integers A[O,... n-1]to express a big integer which is a How to solve the problem? (Master theorem see p 76 less than or equal to 232(n+1-1 but is bigger than 232n7 清华大学 宋斌恒 37 Solution! n Using the merge algorithm we get the solution:{1,3,5,7,9,10,12,21,45} n Any left problems? 清华大学 宋斌恒 38 Correctness n Is your solution correct? n Does your merge algorithm outcome a sorted array in any case? n Is the condition for merge algorithm fulfilled? n How to fulfill the condition? n Using other method n Using the same divide and conquer method n To a trivial state: for example there are only one element for sorting. 清华大学 宋斌恒 39 Complexity Analysis n How many memories does the algorithm use? n How many steps does the algorithm use? n Let T(n) be the number of steps used in the algorithm for an array of length n, then we know that by the divide and conquer that: n T(n)=2T(n/2)+Q(n), where Q is an asymptotic expression means tighten bound, its definition will be given in the next page【我们假设每次均分，而且正好 可以均分】 清华大学 宋斌恒 40 Notation Q n If there exists two positive constants c and d such that when n tends to infinity we have cg(n) ≤ f(n) ≤ dg(n) then we call g(n) is an asymptotically tight bounds of f(n) and denote it as f(n)= Q(g(n)) n Other notations o[not tight upper bound], O[upper bound] and W [lower bound], w[not tight lower bound] can be found in p.41 in the reference book. 清华大学 宋斌恒 41 Left problems n What is the upper bounds and lower bounds for the sorting problem? n How to solve the recursive equality(or inequality)? n T(n)=2T(n/2)+Q(n) n How to converge the above equality to a well posed problem? n How to solve the problem?[Master theorem see p.76] 清华大学 宋斌恒 42 Exercise n Big integer’s expression, addition and multiplication in a 32-bits microcomputer. n How to express a big integer? n We use an n-length of array of integers A[0,… ,n-1] to express a big integer which is less than or equal to 232(n+1)-1 but is bigger than 232n n Attention! We use 232 radix