"EMPIRICAL ANALYSIS"
One of the branch of empirical algorithmic is the "Empirical analysis" which deals with the analysis and characterization of the behavior of algorithm. The idea here is to consider the characteristics and performance of a certain algorithm. That is why empirical analysis is implemented in this case. there are two challenges hat we are facing in empirical analysis.First is to develop a correct and complete implementation. Basically we want to have a built-in programs that is useful to implement a complex algorithm. Second is to "determine the nature of the input data and other factors that have direct influence on the experiments to be performed". This includes all data and other properties in a an experiment. There are 3 basic choices that we are going to use: actual data, random data, or perverse data.
Actual data enable us truly to measure the cost of the program in use; random data assure us that our experiments test the algorithm, not the data; and perverse data assure us that our programs can handle any input presented them.
1. Decide on the basic operation.-Operation which has the most running time of the algorithm-.
2. Decide on the input sample (range, size,...).data in an input sample which includes size,range,etc..
3. Convert the algorithm to a program.-converting the algorithm to a specific programming language
4. Generate a sample of inputs.-Specific sample of inputs-
5. Run the program; record the observed data. data to be observed after running the program
6. Analyze the data. -analysis of empirical data-
"ALGORITHM ANALYSIS"
What is algorithm analysis?
"Algorithm Analysis or Analysis of algorithms" is the framework for comparing algorithms and predicting performance. It also provides proof of the correctness of algorithms, allows for the accurate prediction of program performance, and can be used as a measure of computational complexity.
Why do we need to perform analysis of algorithm?
- To compare different algorithms for the same task
- To predict performance in a new environment
- To set values of algorithm parameters
In conducting analysis of algorithm, what are we going to analyze?
In analysis of algorithm, We can:
- determine the running time of a program as a function of its inputs;
- determine the total or maximum memory space needed for program data;
- determine the total size of the program code;
- determine whether the program correctly computes the desired result;
- determine the complexity of the program--e.g., how easy is it to read, understand, and modify; and,
- determine the robustness of the program--e.g., how well does it deal with unexpected or erroneous inputs?
Factors that affect the running time of a program:
- the hardware:
- processor used (type and speed),
- memory available (cache and RAM), and
- disk available;
- the programming language in which the algorithm is specified;
- the language compiler/interpreter used; and
- the computer operating system software.
"BIG-Oh NOTATION"
What is Big-Oh Notation?
An O-notation, or "big-Oh notation is a mathematical artifact that allows us to suppress detail when we are analyzing algorithms. Technically speaking, it is "A function g(N) is said to be O(f(N)) if there exist constants c0 and N0 such that g(N) < c0f(N) for all N > N0".
Why do we use the O-notation?
- To bound the error that we make when we ignore small terms in mathematical formulas
- To bound the error that we make when we ignore parts of a program that contribute a small amount to the total being analyzed
- To allow us to classify algorithms according to upper bounds on their total running times
Big Oh Expressions
Concrete examples for Big-Oh Notation
*Constant time. Running time is O(1).
Elementary operations includes Function call,Boolean operation,Arithmetic operation,Assignment statement and Access array element by index.
Elementary operations includes Function call,Boolean operation,Arithmetic operation,Assignment statement and Access array element by index.
*Logarithmic time. Running time is O (log N).
Searching in a sorted list. Given a sorted array of items, find index of query item.
O(log N) solution. Binary search.
public static int binarySearch(String[] a, String key) {
int left = 0;
int right = a.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int cmp = key.compareTo(a[mid]);
if (cmp < 0) right = mid - 1;
else if (cmp > 0) left = mid + 1;
else return mid;
}
return -1;
}
Searching in a sorted list. Given a sorted array of items, find index of query item.
O(log N) solution. Binary search.
public static int binarySearch(String[] a, String key) {
int left = 0;
int right = a.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int cmp = key.compareTo(a[mid]);
if (cmp < 0) right = mid - 1;
else if (cmp > 0) left = mid + 1;
else return mid;
}
return -1;
}
*Linear time. Running time is O(N).
Find the maximum. Find the maximum value of N items in an array.
double max = Double.NEGATIVE_INFINITY;
for (int i = 0; i < N; i++) {
if (a[i] > max)
max = a[i];
}
Find the maximum. Find the maximum value of N items in an array.
double max = Double.NEGATIVE_INFINITY;
for (int i = 0; i < N; i++) {
if (a[i] > max)
max = a[i];
}
*Quadratic time. Running time is O(N 2 ).
Closest pair of points. Given N points in the plane, find closest pair.
~c N2 solution. Enumerate all pairs of points.
double min = Double.POSITIVE_INFINITY;
for (int i = 0; i < N; i++){
for (int j = i+1; j < N; j++) {
double dx = (x[i] - x[j]);
double dy = (y[i] - y[j]);
if (dx*dx + dy*dy < min)
min = dx*dx + dy*dy;
}
}
Closest pair of points. Given N points in the plane, find closest pair.
~c N2 solution. Enumerate all pairs of points.
double min = Double.POSITIVE_INFINITY;
for (int i = 0; i < N; i++){
for (int j = i+1; j < N; j++) {
double dx = (x[i] - x[j]);
double dy = (y[i] - y[j]);
if (dx*dx + dy*dy < min)
min = dx*dx + dy*dy;
}
}
*Linearithmic time. Running time is O(N log N).
Sorting. Given an array of N elements, rearrange in ascending order.
~c N log N solution. Mergesort.
Sorting. Given an array of N elements, rearrange in ascending order.
~c N log N solution. Mergesort.
*Exponential time. Running time is O(a N
Finbonacci sequence: 1 1 2 3 5 8 13 21 34 55 …
Finbonacci sequence: 1 1 2 3 5 8 13 21 34 55 …
public static int F(int N) {
if (n == 0 || n == 1) return n;
else return F(n-1) + F(n-2);
}
if (n == 0 || n == 1) return n;
else return F(n-1) + F(n-2);
}
Properties of Big-Oh expressions
Complexity Description
1 Constant algorithm is independent of input size.
log N Logarithmic algorithm gets slightly slower as N
grows.
N Linear algorithm is optimal if you need to process
N inputs.
N inputs.
N log N Linearithmic algorithm scales to huge problems.
N 2 Quadratic algorithm practical for use only on
relatively small problems.
relatively small problems.
2N Exponential algorithm is not usually practical.
To know more about this topic, visit the following sites below.
http://www.cameron.edu/~moinian/cs3713/slide-2.6.pdf
http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/03Analysis.pdf
http://www.answers.com/topic/analysis-of-algorithms
http://www.answers.com/topic/empirical-algorithmics
http://www.brpreiss.com/books/opus4/html/page34.html
http://www.zanshu.com/ebook/5_algorithms-in-java-parts-1-4-third-edition/ch02lev1sec1.htm
http://www.zanshu.com/ebook/5_algorithms-in-java-parts-1-4-third-edition/ch02lev1sec2.htm
http://www.zanshu.com/ebook/5_algorithms-in-java-parts-1-4-third-edition/ch02lev1sec4.htm
No comments:
Post a Comment