1. EMPERICAL ANALYSIS
Actually konti lang ang na-search ko tungkol sa empirical analysis. According to my research, Empirical Analysis is one of the two ways to approach analysis of algorithm. Empirical analysis repeatedly run algorithm with different inputs - get some idea of behavior on different sizes of input.
Empirical analysis is important because it helps us to understand and compare algorithms for specific situations. The Mathematical Analysis of some (even very simple) algorithm is very difficult and empirical analysis is the principal alternative.
So, may anim na steps in doing Empirical Analysis:
1.) Decide on the basic operation.
2.) Decide on the input sample(range, size...).
3.) Convert the algorithm to a program.
4.) Generate a sample of inputs.
5.) Run the program and record the observed data.
6.) Analyze the data.
2. ANALYSIS OF ALGORITHM
Algorithm analysis is a field of computer science that is dedicated to understanding the complexity of algorithms. An algorithm is a set of simple instructions to be followed to solve a problem. To analyze an algorithm is to determine the amount of resources such as time and storage necessary to execute it.
When developing solutions to problems we are often faced with multiple approaches that produce the same results. We need to be able to decide which of the options is best suited to our needs. And we can make better decisions if we can characterize the algorithms according to their efficiency.
To characterize algorithm there are two main considerations that we need to consider:
- the amount of storage (memory) that they require while executing.
- the speed with which they complete their task.
But also we need to consider that each algorithm may have different characteristics in different situations. For example, sorting algorithm A may be better than B for small amounts of data, but the situation reversed for large amounts of data. Or A may be better when the data is partially sorted, B otherwise.
Algorithms can be expressed in many ways, in flowcharts, a natural language, and computer programming languages. Algorithms are used in mathematics, computing and linguistics, but a most common use is in computers to do calculations or process data.
Algorithm analysis deals with algorithms written in computer programming languages, which are based on mathematical formalism. An algorithm is essentially a set of instructions for a computer to perform a calculation in a certain way.
One way to test an algorithm is to run a computer program and see how well it works. The problem with this approach is that it only tells us how well the algorithm works with a particular computer and set of inputs. The purpose of algorithm analysis is to test and then draw conclusions about how well a particular algorithm works in general. This would be very difficult and time consuming to do on individual computers, so researchers devise models of computer functioning to test algorithms.
In general, algorithm analysis is most concerned with finding out how much time a program takes to run, and how much memory storage space it needs to execute the program. In particular, computer scientists use algorithm analysis to determine how the data imputed into a program affects its total running time, how much memory space the computer needs for program data, how much space the program’s code takes in the computer, whether an algorithm produces correct calculations, how complex a program is, and how well it deals with unexpected results.
3. BIG-OH NOTATION
Big-O notation is a mathematical description of an algorithm. It is a tool for comparing the growth rate of functions and it allows us to describe an algorithm with respect to its time and space requirements.
The time efficiency of the algorithms can be characterized by only a few growth rate functions:
I. O(l) - Constant Time
– all instructions are executed a fixed number of times, regardless of the size of the input.
Example: taking the head of a list.
II. O(n) - Linear Time
- a constant amount of processing is done on each input element.
Example: searching unordered list.
III. O(n2) - Quadratic Time
– the number of operations is proportional to the size of the task squared.
Example: comparing two two-dimensional arrays of size n by n.
IV. O(log n) - Logarithmic Time
- program gets only slightly slower as n grows (typically by using some transformation that progressively cuts down the size of the problem).
Example: binary search.
V. O(n log n) - "n log n " Time
- Typical of ‘divide and conquer’ algorithms, where the problem is solved by breaking it up into smaller subproblems, solving them independently, then combining the solutions.
Example: mergesort.
VI. O(an) (a > 1) - Exponential Time
- very fast-growing (assuming a>1), essentially unusable for all but very small instances.
Example: Towers of
VII. O(nk) – Polynomial Time
- most often arises from the presence of k nested loops (examples: insertionsort (k=2); Gaussian elimination method for a calculating a determinant (k=3); also typical of ‘greedy algorithms’
Examples: Prim’s and Kruskal’s algorithms.
VIII. O(n!) – Factorial Time
- even worse!
Example: recursive evaluation of a determinant.
The best time in the above list is obviously constant time, and the worst is exponential time which, as we have seen, quickly overwhelms even the fastest computers even for relatively small n. Polynomial growth (linear, quadratic, cubic, etc.) is considered manageable as compared to exponential growth.
No comments:
Post a Comment