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
2.1 The Analysis Framework
Time efficiency and space efficiency
Time efficiency, also called time complexity,
indicates how fast an algorithm in question runs
Space efficiency, also called space
complexity, refers to the amount of memory units required by the algorithm in addition to the space needed for its input and output
Measuring an Input`s size
Almost all algorithms run longer on
larger inputs
Orders of Growth
Algorithms that require an exponential number of operations are practical
for solving only problems of very small sizes.
Worst-Case, Best-Case, and Average-Case Efficiencies
is its efficiency for the worst-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size.
Resume
5 more items...
Framework for evaluating algorithm performance.
2.2 Asymptotic Notations and Basic Efficiency Classes
As pointed out in the previous section, the efficiency analysis framework concentrates on the order of growth of an algorithm’s basic operation count as the
principal indicator of the algorithm’s efficiency.
O-notation
A function t (n) is said to be in O(g(n)), denoted t (n) ∈ O(g(n)),
if t (n) is bounded above by some constant multiple of g(n) for all large n, i.e., if
there exist some positive constant c and some nonnegative integer n0
2.3 Mathematical Analysis of Nonrecursive Algorithms
In this section, we systematically apply the general framework outlined in Section 2.1 to analyzing the time efficiency of nonrecursive algorithms. Let us start with a very simple example that demonstrates all the principal steps typically taken in analyzing such algorithms.
2.4 Mathematical Analysis of Recursive Algorithms | EXAMPLE 1
In this section, we will see how to apply the general framework for analysis of algorithms to recursive algorithms. We start with an example often used to introduce novices to the idea of a recursive algorithm.
General Plan for Analyzing the Time Efficiency of Recursive Algorithms
Decide on a parameter (or parameters) indicating an input’s size.
Identify the algorithm’s basic operation.
2.4 Mathematical Analysis of Recursive Algorithms 73
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.
2.6 Empirical Analysis of Algorithms
The principal alternative to the mathematical analysis of an algorithm’s efficiency is its empirical analysis. This approach implies steps spelled out in the
following plan
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.
2.6 Empirical Analysis of Algorithms 85
Generate a sample of inputs.
Run the algorithm (or algorithms) on the sample’s inputs and record the data observed
Analyze the data obtained.
2.7 Algorithm Visualization
the use of images to convey some useful information about algorithms.
That information can be a visual illustration of an algorithm’s operation, of its performance on different kinds of inputs, or of its execution speed versus that of other algorithms for the same problem
-Static algorithm visualization
-Dynamic algorithm visualization, also called algorithm animation
There are two kinds of algorithm efficiency: time efficiency and space
efficiency. Time efficiency indicates how fast the algorithm runs; space
efficiency deals with the extra space it requires.
An algorithm’s time efficiency is principally measured as a function of its input
size by counting the number of times its basic operation is executed. A basic
operation is the operation that contributes the most to running time. Typically,
it is the most time-consuming operation in the algorithm’s innermost loop.
For some algorithms, the running time can differ considerably for inputs of
the same size, leading to worst-case efficiency, average-case efficiency, and
best-case efficiency.
The established framework for analyzing time efficiency is primarily grounded
in the order of growth of the algorithm’s running time as its input size goes to
infinity.
Summary 95
The notations O, , and are used to indicate and compare the asymptotic
orders of growth of functions expressing algorithm efficiencies.
The efficiencies of a large number of algorithms fall into the following
few classes: constant, logarithmic, linear, linearithmic, quadratic, cubic, and
exponential.
The main tool for analyzing the time efficiency of a nonrecursive algorithm
is to set up a sum expressing the number of executions of its basic operation
and ascertain the sum’s order of growth.
The main tool for analyzing the time efficiency of a recursive algorithm is to
set up a recurrence relation expressing the number of executions of its basic
operation and ascertain the solution’s order of growth.
Succinctness of a recursive algorithm may mask its inefficiency.
The Fibonacci numbers are an important sequence of integers in which every
element is equal to the sum of its two immediate predecessors. There are
several algorithms for computing the Fibonacci numbers, with drastically
different efficiencies.
Empirical analysis of an algorithm is performed by running a program
implementing the algorithm on a sample of inputs and analyzing the data
observed (the basic operation’s count or physical running time). This
often involves generating pseudorandom numbers. The applicability to any
algorithm is the principal strength of this approach; the dependence of results
on the particular computer and instance sample is its main weakness.
Algorithm visualization is the use of images to convey useful information
about algorithms. The two principal variations of algorithm visualization are
static algorithm visualization and dynamic algorithm visualization (also called
algorithm animation).