CS代考 COMP90038 – cscodehelp代写

COMP90038
Algorithms and Complexity
Lecture 4: Analysis of Algorithms (with thanks to Harald Søndergaard)

DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray

Last Time: Time Complexity
Measure input size by natural number n Measure execution time as number of basic
How to compare different t(n) ? Asymptotic growth rate
O(g(n)), Ω(g(n)), Θ(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
• •
operations performed
Time complexity t(n) for an algorithm: number of
•
basic operations as a function of n
•
•
2
•

Establishing Growth Rate
•
•
•
A more common approach uses
In the last lecture we proved t(n) ∈ O(g(n)) for some n >n0 ⇒ t(n) < c ·g(n) for some c and n0. • cases of t and g, using the definition of O directly: lim f(n) = { 0 n→∞ g(n) c f grows asymptotically slower than g f and g have same order of growth f grows asymptotically faster than g 3 Use this to show that 1000n ∈ O(n2) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License ∞ 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 1000n ∈ O(n2) lim 1000n n2 1000 = =0 n n→∞ lim n→∞ So 1000n grows asymptotically slower than n2 Thus 1000n ∈ O(n2) 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License O, Ω, Θ What this tells us about how f(n) relates to • f(n) lim g(n) = { 0 c ∞ f grows asymptotically slower than g f and g have same order of growth f grows asymptotically faster than g ∈ ) ∈ ∈ Ω( ( ( g g g O(g(n)), Ω(g(n)) and Θ(g(n)) n→∞ f f f ( ( ( n n n ) ) ) O Θ ( ( ( n n n ) ) ) ) ) L’Hôpital’s Rule lim t(n) = lim t′(n) h→∞ g(n) h→∞ g′(n) where t’ and g’ are the derivatives of t and g For example, show that log2 n grows slower than • lim n→∞ log n 2 1 (loge 2)n n =lim 1⋅1⋅2n = lim n→∞ 1 2n n→∞(log2 n ) e n = 2 lim n = 2 lim 1 =0 6 loge 2 n→∞ n loge 2 n→∞ n Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Finding Largest Element in an Array A: max: 246293 0123456 A[i] (where n is length of the array) 23 12 42 6 69 18 3 8 Example: Finding Largest Element in an Array (where n is length of the array) Size of input, n: length of the array Basic operation: comparison “A[i] > max”
Count the number of basic operations executed for an array of size n:
n−1
C(n) = ∑ 1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)
i=1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
23
12
42
6
69
18
3
0123456
A[i] A[j]
9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
min: 3601

Example: Selection Sort
3
12
42
6
69
18
23
0123456
A[i]
10 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
min: 036

Example: Selection Sort
3
12
42
6
69
18
23
0123456
A[i] A[j]
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
min: 13

Example: Selection Sort
3
6
42
12
69
18
23
0123456
A[i]
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
min: 03

Example: Selection Sort
Basic operation: comparison A[j] < A[min] n−2 n−1 n−2 n−2 n−2 C(n) =∑ ∑ 1 = ∑ (n − 1 − i) = ∑ (n − 1) − ∑ i i=0 j=i+1 =(n−1)2−(n−2)(n−1) =n(n−1)∈Θ(n2) 22 Input size n: length of the array i=0 i=0 i=0 13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 0 k:10 57 82 1403 34 96 ABC 14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication i: 0 j: 1 k:10 57 82 10351020 34 96 ABC 15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication Basic operation: multiplication A[i,k] * B[k,j] n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Matrix Multiplication n−1 n−1 n−1 M(n) = ∑∑∑1 i=0 j=0 k=0 n−1 n−1 n−1 n−1 n−1 n−1 =∑∑((n−1)−0+1) =∑∑n =∑∑(n⋅1) i=0 j=0 i=0 = n3 ∈ Θ(n3) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License i=0 j=0 i=0 j=0 17 n−1 2 =∑ n⋅∑1 =∑n n−1 n−1 i=0 j=0 Analysing Recursive Algorithms F(5) =F(4)⋅5 = (F(3) ⋅ 4) ⋅ 5 = ((F(2) ⋅ 3) ⋅ 4) ⋅ 5 = (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((F(0) ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((1 ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = 5! 18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Analysing Recursive Algorithms We express the cost recursively (as a recurrence relation) M(0)= 0 M(n)= M(n−1)+1 Need to express M(n) in closed form (i.e. non-recursively) Try: “telescoping” aka “backward substitution” 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Basic operation: multiplication Telescoping (aka Backward Substitution) M(n) = M(n − 1) + 1 What is M(n-1) ? M(n)= (M(n−2)+1)+1 = M(n − 2) + 2 M(0) = 0 M(n − 1) = M((n − 1) − 1) + 1 = (M(n − 3) + 1) + 2 = M(n − 3) + 3 = M(n − 2) + 1 Closed form: 20 ... = M(n − n) + n M(n) = n Complexity: = M(0) + n M(n) ∈ Θ(n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License =n 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Binary Search in Sorted Array A: BinSearch(A,0,6,41) BinSearch(A,4,6,41) 0123456 lo: 0 hi: 6 key: 41 mid: 3 4 9 13 22 41 83 96 22 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Binary Search in Sorted Array A: BinSearch(A,4,6,41) BinSearch(A,4,4,41) 0123456 lo: 4 hi: 6 key: 41 mid: 5 4 9 13 22 41 83 96 23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example: Binary Search in Sorted Array A: BinSearch(A,4,4,41) returns 4 0123456 lo: 4 hi: 4 key: 41 mid: 4 4 9 13 22 41 83 96 Example: Binary Search in Sorted Array Basic operation: key comparison A[mid] = key C(n) = C(n/2) + 1 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License C(0) = 0 Telescoping A smoothness rule allows us to assume that n is a power of 2 C(0) = 0 C(n) = C(n/2) + 1 C(n) = C(n/2) + 1 = (C(n/4) + 1) + 1 = ((C(n/8) + 1) + 1) + 1 ... C(n) ∈ Θ(log n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License = C(n/n) + log2 n = (C(0) + 1) + log2 n = 1 + log2 n Logarithmic Functions Have Same Rate of Growth In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is Asymptotically, all logarithmic behaviour is the same, since loga x = (loga b)(logb x) lim logan = lim (loga b)(logb n) = (loga b) lim 1 = loga b n→∞ logbn n→∞ logb n n→∞ 26 log nc ∈ Θ(log n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License So, e.g.: Also, since log nc = c ⋅ log n Θ(logan) = Θ(logbn) Back to Euclid Running time is linear in size (in bits) of input, i.e. O(log(m + n)) since the value of m (and n) is at least halved in every two iterations. Why? After two iterations, m becomes m mod n; also 1