Please enable JavaScript.
Coggle requires JavaScript to display documents.
Fundamentals of the Analysis of Algorithm Efficiency - Coggle Diagram
Fundamentals of the Analysis of Algorithm Efficiency
The Analysis Framework
It has come to attention that algorithms should be anylised to better understand its uses
An algorithm can be anylised in two different main aspects
Space complexity
Space complexity refers to the amount of memory that a certain algorythm uses when running
Time Complexity
Time complexity refers to the amount of time that an algorithm takes to solve a given problem
The best way to anylise it is to do a function of given the size of the : vector, list , matriz etc being anysed the result will vary
Usualy a good algorith is of a time complexity of (n * log(n)) or lower ( merge sort and quick sort being examples of algorithms of a low time complexity)
A given algorithm can be anylised in 3 diferent cases: Best case , Avarege Case and worst case
"Amortizing" the algorithm
Some times the cost of doing a single operation in a given algorithm is really high , however when the same algorithm is given bigger and bigger outputs the sheer size of the array for example can compensate for the high cost of a single operation
Algorithm Visualization
Analysis
Empirical Analysis
A general plan for empirical analyses
Understand the experiment’s purpose.
Decide on the efficiency metric M to be measured and the measurement unit
(an operation count vs. a time unit).
Decide on characteristics of the input sample (its range, size, and so on).
Prepare a program implementing the algorithm (or algorithms) for the experimentation.
Generate a sample of inputs.
Run the algorithm (or algorithms) on the sample’s inputs and record the data
observed.
Analyze the data obtained.
Mathematical Analysis
Nonrecursive Algorithms
Step by Step plan to analise the amount of basic operations on a nonrecursive algorithm
Decide on a parameter (or parameters) indicating an input’s size.
Identify the algorithm’s basic operation. (As a rule, it is located in the innermost loop.)
Check whether the number of times the basic operation is executed depends
only on the size of an input. If it also depends on some additional property,
the worst-case, average-case, and, if necessary, best-case efficiencies have to
be investigated separately.
Set up a sum expressing the number of times the algorithm’s basic operation
is executed.4
Using standard formulas and rules of sum manipulation, either find a closedform formula for the count or, at the very least, establish its order of growth.
Recursive Algorithms
Step by Step plan to analise the amount of basic operations on a recursive algorithm
Decide on a parameter (or parameters) indicating an input’s size.
Identify the algorithm’s basic operation.
Check whether the number of times the basic operation is executed can vary
on different inputs of the same size; if it can, the worst-case, average-case, and
best-case efficiencies must be investigated separately.
Set up a recurrence relation, with an appropriate initial condition, for the
number of times the basic operation is executed.
Solve the recurrence or, at least, ascertain the order of growth of its solution.
Asymptotic Notations and Basic Efficiency Classes
There are 3 types of effiency classes : The big O notation, The big OMEGA notation, And the big TETA notation
Big O notation
Stand for the functions that have a order smaller than the one thats depicted after it
Big OMEGA notation
Stands for the functions that have an order equal to or bigger than the one depicted after it
Big TETA notation
Stands for the functions that have an order equal to the one depicted after it