2. Analysis of Algorithms Flashcards
The very same approach that scientists use to understand the natural world is effective for studying the running time of programs:
!Observe some feature of the natural world, generally with precise measurements.
!Hypothesize a model that is consistent with the observations.
!Predict events using the hypothesis.
!Verify the predictions by making further observations.
!Validate by repeating until the hypothesis and observations agree.
The experiments we design must be ___ and the hypotheses that we formulate must be _____.
The experiments we design must be REPRODUCIBLE and the hypotheses that we formulate must be FALSIFIABLE.
Mathematical models.
The total running time of a program is determined by two primary factors: the cost of executing each statement and the frequency of execution of each statement.
Tilde approximations
We use tilde approximations, where we throw away low-order terms that complicate formulas. We write ~ f(N) to represent any function that when divided by f(N) approaches 1 as N grows. We write g(N) ~ f(N) to indicate that g(N) / f(N) approaches 1 as N grows.
function:
(n^3/6)-(n^2/2)+(n/3)
lgN+1
3
tilde approximation:
tilde approximation:
n^3/6
lgN
3
Order-of-growth classifications.
very often the order of growth of the cost is one of just a few functions of the problem size N.
function:
(n^3/6)-(n^2/2)+(n/3)
lgN+1
3
order of growth:
order of growth:
n^3
lgN
1
Cost model
We focus attention on properties of algorithms by articulating(формулируя) a cost model that defines the basic operations. For example, an appropriate cost model for the 3-sum problem is the number of times we access an array entry, for read or write.
The order of growth of the running time of:
public class ThreeSum {
private ThreeSum() { }
public static void printAll(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
for (int k = j+1; k < n; k++) {
if (a[i] + a[j] + a[k] == 0) {
StdOut.println(a[i] + " " + a[j] + " " + a[k]);
}
}
}
}
}
public static int count(int[] a) {
int n = a.length;
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
for (int k = j+1; k < n; k++) {
if (a[i] + a[j] + a[k] == 0) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
In in = new In(args[0]);
int[] a = in.readAllInts();
Stopwatch timer = new Stopwatch();
int count = count(a);
StdOut.println("elapsed time = " + timer.elapsedTime());
StdOut.println(count);
}
is N^3.
The brute-force 3-sum algorithm uses ~ ____ array accesses to compute the number of triples that sum to 0 among N numbers.
N^3 / 2
Input models.
We can carefully model the kind of input to be processed. This approach is challenging because the model may be unrealistic
Worst-case performance guarantees.
Running time of a program is less than a certain bound (as a function of the input size), no matter what the input. Such a conservative approach might be appropriate for the software that runs a nuclear reactor or a pacemaker or the brakes in your car.
Randomized algorithms.
One way to provide a performance guarantee is to introduce randomness, e.g., quicksort and hashing. Every time you run the algorithm, it will take a different amount of time. These guarantees are not absolute, but the chance that they are invalid is less than the chance your computer will be struck by lightning. Thus, such guarantees are as useful in practice as worst-case guarantees.
Amortized analysis.
For many applications, the algorithm input might be not just data, but the sequence of operations performed by the client. Amortized analysis provides a worst-case performance guarantee on a sequence of operations.
In the linked-list implementation of Bag, Stack, and Queue, all operations take
constant time in the worst case.
