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.
AMBIENT/
Chủ đề:
Nội dung Text: 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 6.1
- 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 & a,
5 int & seqstart, int & seqEnd )
6 (
7 int n = a.size( );
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 6.2
- Linear Algorithm
Continued….
- Theorem 6.3
- 1 // Linear maximum contiguous subsequence sum
algorithm.
2 // seqStart and seqEnd represent the actual best
sequence.
3 template
4 Comparable maxSubsequenceSum( const
vector & a,
5 int & seqstart, int & seqEnd )
6 {
7 int n = a. size ( ) ;
8 Comparable thissum = 0;
9 Comparable maxSum = 0;
- Linear Algorithm
Continued….
According to Theorem 6.3 when a negative subsequence
is detected, not only can we break the inner loop, but we
can also advance i to j + 1
The running time of this algorithm is linear: At each step
in the loop, we advance j, so the loop iterates at most N
times
The correctness of this algorithm is much less obvious
than for the previous algorithms, which is typical. That is,
algorithms that use the structure of a problem to beat an
exhaustive search generally require some sort of
correctness proof
We proved that the algorithm is correct by using a short
- General BigOh Rules
- BigOh Notation
- BigOmega Notation
- BigTheta Notation
- LittleOh Notation
- Summary of Four Definition
- Running Time of Algorithms
The running time of statements inside a group of nested
loops is the running time of the statements multiplied by
the sizes of all the loops
The running time of a sequence of consecutive loops is
the running time of the dominant loop
The time difference between a nested loop in which both
indices run from 1 to N and two consecutive loops that are
not nested but run over the same indices is the same as the
space difference between a twodimensional array and two
onedimensional arrays
The first case is quadratic
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
