03.key
http://people.eng.unimelb.edu.au/tobym
@tobycmurray
DMD 8.17 (Level 8, Doug McDonell Bldg)
Toby Murray
COMP90038
Algorithms and Complexity
Lecture 3: Growth Rate and Algorithm Efficiency
(with thanks to Harald Søndergaard)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Update
• Compulsory Quizzes (first one closes Tuesday Week 3)
• Tutorials start this week
• Background knowledge catch-up tutorials:
• Weeks 2 and 3
• Thursday 1-2pm and 2:15-3:15pm
Alice Hoy, Room 101
• Consultation Hours
• Discussion Board
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Algorithm Efficiency
3
Why is one more efficient than the other?
What does “efficient” even mean?
How can we talk about these things precisely?
Two algorithms for computing gcd:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Linear Search Example
4
function find(A,x,n)
j ← 0
while j < nif A[j] = xreturn jj ← j+1return -1 Y:Let’s trace the execution of find(Y,7,7)j: 0A[j]n: 7x: 7A: Y j: 1j: 2j: 3j: 4(returns 4)Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseLinear Search Example 5function find(A,x,n)j ← 0while j < nif A[j] = xreturn jj ← j+1return -1 How many times does the loop run to find 7?5.How many times does the loop run to find 6? 1.How many times does the loop run to find 99? 7.(the length of the array)Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseAssessing Algorithm “Efficiency”• Resources consumed: time and space • We want to assess efficiency as a function of input size • Mathematical vs empirical assessment • Average case vs worst case • Knowledge about input peculiarities may affect the choice of algorithm • The right choice of algorithm may also depend on the programming language used for implementation 6Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseRunning Time Dependencies• There are many things that a program’s running time depends on: 1.Complexity of the algorithms used 2.Input to the program 3.Underlying machine, including memory architecture 4.Language/compiler/operating system • Since we want to compare algorithms we ignore (3) and (4); just consider units of time • Use a natural number n to quantify (2)—size of the input • Express (1) as a function of n 7Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseLinear Search Example 8function find(A,x,n)j ← 0while j < nif A[j] = xreturn jj ← j+1return -1 How should we measure the size, n,
of the input to this algorithm?n = the length of the arrayHow should we quantify the cost to run this algorithm? roughly, number of times the loop runs
(later in this lecture we will be more precise)Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseLinear Search Example 9function find(A,x,n)j ← 0while j < nif A[j] = xreturn jj ← j+1return -1 What is the worst case input?an array that doesn’t contain the item, x, we are searching forWorst case time complexity: n (since the loop runs n times in that case)Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseLinear Search Example 10function find(A,x,n)j ← 0while j < nif A[j] = xreturn jj ← j+1return -1 What is the best case input?an array that has the item, x, we are searching for in the first positionBest case time complexity: 1 (since the loop runs once in that case)Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseEstimating Time Consumption• Number of loop iterations is not a good estimate of running time.• Better is to identify the algorithm’s basic operation and how many times it is performed • If c is the cost of a basic operation and g(n) is the number of times the operation is performed for input size n,
then running time t(n)≈c ⋅ g(n) 11Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseLinear Search Example 12function find(A,x,n)j ← 0while j < nif A[j] = xreturn jj ← j+1return -1 What is the basic operation here?the comparison A[j] = xRule of thumb: the most expensive operation executed each time in the inner-most loop of the programCopyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseExamples: Input Size and Basic Operation 13Problem Size Measure Basic OperationSearch in a list
of n items n Key comparisonMultiply two matrices of floatsMatrix size
(rows x columns) Float multiplicationCompute an log n Float multiplicationGraph problem Number of nodes and edges Visiting a nodeCopyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseBest, Average and Worst Case• The running time t(n) may well depend on more than just n • Worse case: analysis makes the most pessimistic assumptions about the input • Best case: analysis makes the most optimistic assumptions about the input • Average case: analysis aims to find the expected running time across all possible input of size n
(Note: not an average of the worst and best cases) • Amortised analysis takes context of running an algorithm into account, calculates cost spread over many runs. Used for “self-organising” data structures that adapt to their usage14Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseLarge Input is what Matters• Small input does not properly stress an algorithm
for small values of m and n, their cost is similar
• Only as we let m and n grow large do we witness (big) differences inperformance.15Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseGuessing Game Example• Guess which number I am thinking of, between 1 and n (inclusive). I will tell you if it is higher or lower than each guess. 161 10050Wrong. My number is higher than 50.51 75Wrong. My number is lower than 75.We are halving the search space each time.Basic operation: guessing a number.(Worse case) complexity: log nCopyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseThe Tyranny of Growth Rate 17n log2 n n n log2 n n2 n3 2n n!101 3 101 3 ·101 102 103 103 4 · 106102 7 102 7 · 102 104 106 1030 9 · 10157103 10 103 1 · 104 106 109 – -1030 is 1,000 times the number of nano-seconds since the Big Bang. At a rate of a trillion (1012) operations per second, executing 2100
operations would take a computer in the order of 1010 years. That is more than the estimated age of the Earth Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseThe Tyranny of Growth Rate 18Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseFunctions Often Met in
Algorithm Classification• 1: Running time independent of input • log n: typical for “divide an conquer” solutions, for example lookup in a balanced search tree • Linear (n): When each input must be processed once • n log n: Each input element processed once and processing involves other elements too, for example, sorting. • n2, n3: Quadratic, cubic. Processing all pairs (triples) of elements. •2n: Exponential. Processing all subsets of elements. 19Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseAsymptotic Analysis• We are interested in the growth rate of functions • Ignore constant factors • Ignore small input sizes 20Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseAsymptotics• f(n) ≺ g(n)ifflim= 0 • That is, g approaches infinity faster than f • 1 ≺ log n ≺ nε≺ nc ≺ nlog n ≺ cn ≺ nn
where 0 < ε < 1 < c• In asymptotic analysis, think big! • e.g., log n ≺ n0.0001, even though forn = 10100, 100 > 1.023.
• Try it for n = 101000000
21
n→∞
f(n)
g(n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Big-Oh Notation
• O(g(n)) denotes the set of functions that grow no
faster than g, asymptotically.
• Formal definition: We write
t(n) ∈ O(g(n))
when, for some c and n0
n > n0⇒t(n) < c ·g(n)• For example: 1 + 2 + … + n ∈ O(n2) 22Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseBig-Oh: What t(n) ∈ O(g(n)) Means 23Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseBig-Oh Pitfalls• Levitin’s notation t(n) ∈ O(g(n)) is meaningful, but not standard.• Other authors use t(n) = O(g(n)) for the same thing.• As O provides an upper bound, it is correct to say both 3n ∈ O(n2) and 3n ∈ O(n) (so you can see why using ‘=’ is confusing); the latter, 3n ∈ O(n), is of course more precise and useful.• Note that c and n0 may be large.24Copyright University of Melbourne 2016, provided under Creative Commons Attribution LicenseBig-Omega and Big-Theta• Big Omega: Ω(g(n)) denotes the set of functions that grow no slower than g, asymptotically, so Ω is for lower bounds.• t(n) ∈ Ω(g(n)) iff n >n0⇒t(n) > c ·g(n),
for some n0 and c.
• Big Theta: Θ is for exact order of growth.
• t(n) ∈ Θ(g(n)) iff t(n) ∈ O(g(n)) and t(n) ∈ Ω(g(n)).
25
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Big-Omega: What t(n) ∈ Ω(g(n))Means
26
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Big-Theta: What t(n) ∈ Θ(g(n))Means
27
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Establishing Growth Rate
• We can use the definition of O directly.
t(n) ∈ O(g(n)) iff: n > n0 ⇒ t(n) < c ·g(n)• Exercise: use this to show that 1 + 2 + … + n ∈ O(n2) • Also show that: 17n2 + 85n + 1024 ∈ O(n2)28Copyright University of Melbourne 2016, provided under Creative Commons Attribution License1 + 2 + … + n ∈ O(n2) 291 + 2 + … + n < c · n2Find some c and n0 such that, for all n > n0
1 + 2 + … + n
= n(n+1)
2
=
n2 + n
2
< n2 + n(for n > 0)
< n2 + n2 (for n > 1)
= 2n2 Choose n0 = 1, c = 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
17n2 + 85n + 1024 ∈ O(n2)
30
17n2 + 85n + 1024 < c · n2Find some c and n0 such that, for all n > n0
Guess c = 18
17n2 + 85n + 1024 < 18n2Need to prove:85n + 1024 < n2i.e.Guess n0 = 102485·1024 + 1024 < 1024·1024Check if: 85n0+ 1024 < n02 i.e. 86·1024 < 1024·1024 Clearly true.Choose c = 18, n0 = 1024Copyright University of Melbourne 2016, provided under Creative Commons Attribution License17n2 + 85n + 1024 ∈ O(n2)3117n2 + 85n + 1024 < c · n2Find some c and n0 such that, for all n > n0
Alternative:
17n2 + 85n + 1024
Let c = 17 + 85 + 1024
Choose c = 17 + 85 + 1024, n0 = 1
< 17n2 + 85n2 + 1024n2 (for n > 1)
=(17 + 85 + 1024)n2
Of course, this works for any polynomial.
Reviews
There are no reviews yet.