CMPS 3120 Algorithm Analysis
Analysis of Algorithm Efficiency
Let's try some example on computer, and compare the time used
Fibonacci numbers: are named after Italian mathematician Leonardo of Pisa, later known as Fibonacci. Fibonacci numbers are strongly related to the golden ratio: Binet's formula expresses the nth Fibonacci number in terms of n and the golden ratio, and implies that the ratio of two consecutive Fibonacci numbers tends to the golden ratio as n increases.
- In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation Fn = Fn-1 + Fn-2 with seed values F0 = 0 and F1 = 1.
- The beginning of the sequence is thus:
- (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
Here are two different Algorithms for Fibonacci, which one is faster?
Fibo1(n)
if n <= 1 then
Return n;
else
Return ( Fibo1(n-1) + Fibo1(n-2) );
Fibo2(n)
f[1] = 1;
f[2] = 1;
for i = 3 ~ n do
f[i] = f[i-1] + f[i-2]
Return f[n]
[1 1] [0 1;1 1]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Two types of algorithm (Iterative vs Recursive)
Compute the Power of an integer: how can we compute bn with recursive algorithm? What's performance difference between following two algorithms?
| def
power(b, n): pow = 1 for i in range(n): pow = pow * b return pow |
def power(b, n): if n == 0: return 1 pow = power(b, n // 2) if n & 1: #odd return b * pow * pow return pow * pow #even |
How to formally calculate algorithm complexity
- Decide on a parameter indicating an input’s size.
- Identify the algorithm’s basic operation.
- Check whether the number of times the basic op. is executed may vary on different inputs of the same size. (If it may, the worst, average, and best cases must be investigated separately.)
- The total number of times the basic op. is executed.
- Find out solution’s order of growth
- Analyzing the complexity of an algorithm (Iterative)
- Analysis of Recursive Algorithms
|
|
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
How to find out the order of growth
- O: Big-Oh
Ω: Big-Omega
Θ: Theta
o: Small-oh
ω: Small-omega - Proof by definition
- Using limits to compare orders of growth
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The Tower of Hanoi: There is a story about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it, surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks in accordance with the immutable rules of Brahma since that time. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle is completed, the world will end.
Mathematically, the Tower of Hanoi is a mathematical puzzle.
It consists of three rods and a number of disks of different
sizes, which can slide onto any rod. The puzzle starts with the
disks in a neat stack in ascending order of size on one rod, the
smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to
another rod, obeying the following simple rules:
1.Only one disk can be moved at a time.
2.Each move consists of taking the upper disk from one of the
stacks and placing it on top of another stack or on an empty
rod.
3.No larger disk may be placed on top of a smaller disk.
If the legend were true, and if the
priests were able to move disks at a rate of one per second,
using the smallest number of moves.
How long will it take to the end
of the world?