This chapter presents the following content: Introduction to algorithm analysis, different functions, function’s growth rate, three problems related to algorithm running time, maximum contiguous subsequence sum problem. | Lecture note Data visualization - Chapter 16 Lecture 16 Recap Introduction to Algorithm Analysis Different Functions Function s Growth Rate Three Problems Related to Algorithm Running Time Find Minimum in an Array Find Closest Point in a Plane Find Collinear Points in a Plane Maximum Contiguous Subsequence Sum Problem Theorem Proof Place the following N 2 balls in a box N balls numbered 1 through N one unnumbered red ball and one unnumbered blue ball. Remove three balls from the box. If a red ball is drawn number it as the lowest of the numbered balls drawn. If a blue ball is drawn number it as highest of the numbered balls drawn. Note that if you draw both a red and a blue ball then the effect is to have three balls identical numbered. Order the three balls. Each such order corresponds to a triplet solution to the 1 Quadratic maximum contiguous subsequence sum algorithm. 2 seqStart and seqEnd represent the actual best sequence. 3 template 4 Comparable maxSubsequenceSum const vector amp a 5 int amp seqstart int amp seqEnd 6 7 int n 8 Comparable maxSum 0 9 Linear Algorithm To move from a quadratic algorithm to a linear algorithm we need to remove yet another loop The problem is that the quadratic algorithm is still an exhaustive search that is we are trying all possible subsequences The only difference between the quadratic and cubic algorithms is that the cost of testing each successive subsequence is a constant O 1 instead of linear O N Because a quadratic number of subsequences are possible the only way we can attain a subquadratic bound is to find a clever way to eliminate from consideration a large Theorem Linear Algorithm Continued . Theorem 1 Linear maximum contiguous subsequence sum algorithm. 2 seqStart and seqEnd represent the actual best sequence. 3 template 4 Comparable maxSubsequenceSum const vector amp a 5 int amp seqstart int amp seqEnd 6 7 int n a. size 8 Comparable thissum 0 9 Comparable maxSum 0 Linear Algorithm Continued . .
