Xem mẫu
- Lecture 17
- Recap
Remaining Part of Maximum Contiguous Subsequence
Sum Problem
General BigOh Rule
BigOh
BigOmega
BigTheta
LittleOh
Running Time of Algorithm
- Running Time of Cubic
Algorithm
- Running Time of Quadratic
Algorithm
- Running Time of Linear
Algorithm
A similar calculation shows that a 10fold increase in
input size results in a 10fold increase in running time
This relationship has been confirmed experimentally
For a linear program the term sufficiently large means a
somewhat higher input size than for the other programs
The reason is that of the overhead of 0.000003 sec is
used in all cases
For a linear program, this term is still significant for
moderate input sizes
- Running Time of Logarithmic
Terms
- The Logarithm
The list of typical growth rate functions includes several
entries containing the logarithm
A logarithm is the exponent that indicates the power to
which a number (the base) is raised to produce a given
number
- Definition of Logarithm
- Theorem 6.4
- Logarithm Continued….
- Bits in a Binary Number
- Repeated Doubling
- Repeated Halving
- Continued….
Many of the algorithms contain logarithms, because of the
repeated halving principle, which holds that, starting at N,
we can halve only logarithmically many times
In other words, an algorithm is O(log N) if it takes
constant (O( 1)) time to cut the problem size by a constant
fraction (usually 112)
This condition follows directly from the fact that there
will be O(log N) iterations of the loop
Any constant fraction will do because the fraction is
reflected in the base of the logarithm, and Theorem 6.4
tells us that the base does not matter
- Theorem 6.5
- Static Searching Problem
An important use of computers is to look up data
If the data are not allowed to change (e.g., it is stored on a
CDROM), we say that the data are static
A static search accesses data that are never altered
- Problem
GIVEN AN INTEGER X AND AN ARRAY A,
RETURN THE POSITION OF X IN A OR AN
INDICATION THAT IT IS NOT PRESENT. IF X
OCCURS MORE THAN ONCE, RETURN ANY
OCCURRENCE. THE ARRAY A IS NEVER
ALTERED.
- Solution
An example of static searching is looking up a person in
the telephone book
The efficiency of a static searching algorithm depends on
whether the array being searched is sorted
In the case of the telephone book, searching by name is
fast, but searching by phone number is hopeless
Some solution
Sequential Search
Binary Search
- Sequential Search
When the input array has not been sorted, we have little
choice but to do a linear sequential search that steps
through the array sequentially until a match is found
The complexity of the algorithm is analyzed in three ways
First, we provide the cost of an unsuccessful search
Second, we give the worstcase cost of a successful search
Finally, we find the average cost of a successful search
Analyzing successful and unsuccessful searches
separately is typical
- Continued….
An unsuccessful search requires the examination of every
item in the array, so the time will be O(N)
In the worst case, a successful search, too, requires the
examination of every item in the array because we might
not find a match until the last item. Thus the worstcase
running time for a successful search is also linear
On average, however, we search only half an array. That
is, for every successful search in position i, there is a
corresponding successful search in position N1i
However, N/2 is still O(N)
nguon tai.lieu . vn
