CMPS 3120 Algorithm Analysis
Analysis of Algorithm Efficiency
Let's try some example on computer, and compare the time used
Sum of N numbers / Gauss’ Trick
(link):
The
story goes that, in school, at the age of 8,
Carl Friedrich Gauss was able to add up the first 100
numbers extremely quickly. I like to think of the teacher as
having used this trick many times to keep the class busy for
long periods while he took a snooze. He knew that he was in for
a long quiet period as the class slaved away. Even if one of
them got an answer, the teacher could ask them to check it to
take up more time. But he hadn’t bargained on this precocious 8
year old.
In a flash Gauss came out with 5050. But not only could he
calculate the sum of the first 100 numbers that quickly, he
could also justify the correctness of his answer.
Check the following 3 algorithms, which one is the fastest?
def sum1(n) :
total = 0
for i in range(n+1):
total += i
return total
def sum2(n) :
if n == 1:
return 1
else:
return sum2(n-1)+n
def sum3(n) :
return n*(1+n)/2
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 "normal" algorithm (Iterative)
- Analysis of Recursive Algorithms
|
|
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
What is the meaning of 10-4???
Ten-codes, officially known as ten signals, are brevity codes used to represent common phrases in voice communication, particularly by US public safety officials and in citizens band (CB) radio transmissions. The police version of ten-codes is officially known as the APCO Project 14 Aural Brevity Code.
Police use 10 codes for indication of the urgency of a situation.
Here is a pic of "Official 10 code coffee cup" I found online.
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?