Please enable JavaScript.
Coggle requires JavaScript to display documents.
The Analysis Framework, Algorithm Visualization, Asymptotic Notations and…
The Analysis Framework
efficiency of algorithms
time efficiency
space efficiency
Measuring and Input size
efficiency of algorithms
Measuring runing time
Orders of Growth
Algorithm Visualization
the use of images to convey some useful information about algorithms
Static algorithm visualization
Dynamic algorithm visualization, also called algorithm animation
gráficos tabelas e outras elementos de visualização
Asymptotic Notations and Basic Efficiency Classes
Notation
asymptotic notations
prove their
general properties
Uso de limites para comprar ordem de crescimento
L’Hopital’s rule é usada (que massa)
Basic Efficiency Classes
Mathematical Analysis of Nonrecursive Algorithms
General Plan for Analyzing
straightforward algorithm
Detalhamento de algoritmos específicos que não cabem aqui
Empirical Analysis of Algorithms
General Plan for the Empirical Analysis of Algorithm Time Efficiency
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.
Analyze the data obtained.
Run the algorithm (or algorithms) on the sample’s inputs and record the data
linear congruential method
Mathematical Analysis of Recursive Algorithms
Compute the factorial function
n!= 1 . ... . (n − 1) . n = (n − 1)!. n for n ≥ 1
and 0!= 1 by definition, we can compute F (n) = F (n − 1) . n with the following
recursive algorithm.
ALGORITHM F(n)
//Computes n! recursively
//Input: A nonnegative integer n
//Output: The value of n!
if n = 0 return 1
else return F (n − 1) ∗ n