CS计算机代考程序代写 algorithm COMP2100/COMP6442

COMP2100/COMP6442
Algorithms Part II
– Lecture 6]
Kin Chau [
Sid Chi
1

Recap from Last Lecture
• Divide-and-conquer
• Example: Merge Sort, Karatsuba Integer Multiplication
• How did we measure the speed of an algorithm?
• Count the number of operations
• How the number scales with respect to the input size • Time complexity of computation
• Karatsuba multiplication scales as n1.6
2

Goals of This Lecture
• Let us formally formulate the time complexity of computation • How to formally measure the running time of an algorithm?
• Big-O, Big-Ω, Big-Θ notations
• General approach of the running time with recursive algorithms • The Master theorem
3

Big
• What do we mean when we measure runtime?
• How long does it take to solve the problem, in seconds or minutes or hours?
• The exact runtime is heavily dependent on the programming language, system architecture, etc.
• But the most factor is the input size (e.g. the number of bits that used in encoding input)
• We want a way to talk about the running time of an algorithm, with respect to the input size
–
O notation
4

Main idea
• Focus on how the runtime scales with n (the input size)
5

Asymptotic Analysis
• How does the running time scale as n gets large?
• One algorithm is “faster” than another if its runtime scales better
with the size of the input
• Pros
• Abstracts away from hardware- and language-specific issues • Makes algorithm analysis much more tractable
• Cons
• Only makes sense if n is large (compared to the constant factors)
• 2100000000000000 n
• is “better” than n2 ?!?!
6

Big
• Big-O means an upper bound
• Let T(n), g(n) be functions of positive integers
• Think of T(n) as the running time: positive and increasing in n
• We say that “T(n) = O(g(n))” if g(n) grows at least as fast as T(n), when
n gets large • Formally,
–
O
T(n) = O(g(n)) 
There exist c, n0 > 0, such that 0  T(n)  c  g(n),
for all n  n0
7

Example
•2n2 +10=O(n2)
T(n) = O(g(n)) 
There exist c, n0 > 0, such that 0  T(n)  c  g(n),
for all n  n0
•Choosec=3,n0 =4
• Then 0  2n2 + 10  3n2, for all n  4
8

Example
•2n2 +10=O(n2)
T(n) = O(g(n)) 
There exist c, n0 > 0, such that 0  T(n)  c  g(n),
for all n  n0
•Choosec=7,n0 =2
• Then 0  2n2 + 10  7n2, for all n  2
9

Example
• n = O(n2)
T(n) = O(g(n)) 
There exist c, n0 > 0, such that 0  T(n)  c  g(n),
for all n  n0
•Choosec=1,n0 =1
• Then 0  n  n2, for all n  1
10

Big
• Big-Ω means an lower bound
• Let T(n), g(n) be functions of positive integers
• Think of T(n) as the running time: positive and increasing in n
• We say that “T(n) = Ω(g(n))” if g(n) grows at most as fast as T(n), when
n gets large • Formally,
–
Ω
T(n) = Ω(g(n)) 
There exist c, n0 > 0, such that c  g(n)  T(n),
for all n  n0
11

Big
• Big-Θ means a tight bound
• Let T(n), g(n) be functions of positive integers
• Think of T(n) as the running time: positive and increasing in n
• We say that “T(n) = Θ(g(n))” if g(n) grows tightly as fast as T(n), when
n gets large • Formally,
–
Θ
T(n) = Θ(g(n)) 
There exist c, c’, n0 > 0, such that c  g(n)  T(n)  c’  g(n),
for all n  n0
12

Example
• 2n2 + 10 = O(n2), 2n2 + 10 = Ω(n2), 2n2 + 10 = Θ(n2) • 2n + 10 = O(n2), 2n + 10  Ω(n2), 2n + 10  Θ(n2)
• 2n2 + 10  O(n), 2n2 + 10 = Ω(n), 2n2 + 10  Θ(n)
• Note that if T(n) = O(g(n)) and T(n) = Ω(g(n)), then T(n) = Θ(g(n)) • Why?
13

Example 1
• What is the running time T(n) of the following procedure? • Assume c() requires constant running time
• T(n) = O(n4)
public void method(int n) {
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { for (int l = 0; l < n; l++) { c(); } } } } 14 Example 2 • What is the running time T(n) of the following procedure? • Assume c() requires constant running time • h = 1, 2, 4, ..., 2log(n) • T(n) = O(log n) public void method(int n) { h=1; } while (h <= n) { c(); h = 2*h; } 15 Example 3 • What is the running time T(n) of the following procedure? • Assume c() requires constant running time • Each inner for-loop (i) gets j times • T(n) = 1+2+...+n = O(n2) public void method(int n) { for (int j = 0; j < n; j++) { for (int i = 0; i < j; i++) { c(); } } } 16 Summing Up • Big-O • T(n) = O(g(n))  there exist c, n0 > 0, such that 0  T(n)  c  g(n), for all n  n0
• Big-Ω
• T(n) = Ω(g(n))  there exist c, n0 > 0, such that c  g(n)  T(n), for all n  n0
• Big-Θ
• T(n) = Θ(g(n))  there exist c, c’, n0 > 0, such that c  g(n)  T(n)  c’  g(n), for
all n  n0
• But we should always be careful not to abuse it
• c =21000000
• n ≥ n =21000000
0 17

Exercise
• Suppose the n is the size of input. Which one of the following algorithms is the fastest?
A. Algorithm A with runtime modelled as T(n) = 3n + n
B. Algorithm B with runtime modelled as T(n) = 2n + 200000 C. Algorithm C with runtime modelled as T(n) = n1.1
• Which one of the following is INCORRECT?
A. 2n2 + 1000010000 is in O(2n2)
B. 2n2 + n + 100 is in O(n3)
C. 0.1n2 is in O(n log(n))
D. 2n2 + 10 is in O(n2)
18

The Master Theorem
• Recursive integer multiplication • T(n) = 4 T(n/2) + O(n)
• T(n) = O(n2)
• Karatsuba integer multiplication • T(n) = 3 T(n/2) + O(n)
• T(n) = O(nlog(3))  O(n1.6)
• What’s the pattern?
• A formula that solves recurrences when all of sub-problems are the same size • “Generalized” tree method
19

The Master Theorem
• The master theorem applies to recurrence form: T(n) = aT(n/b) + O(nd),
where a  1, b > 1
• a: number of subproblems
• b: factor by which input size shrinks
• d: need to do nd work to create all the subproblems and combine their solution
• Case 1: If a = bd, then T(n) = O(nd log(n)) • Case 2: If a < bd, thenT(n) = O(nd) • Case 3: If a > bd, then T(n) = O(nlogb(a))
20

Example
• T(n) = T(n/2) + O(1)
• a = 1, b = 2, d = 0  a = bd • Hence, T(n) = O(log(n))
• T(n) = 2T(n/2) + O(1)
• a = 2, b = 2, d = 0  a > bd • Hence, T(n) = O(n)
• T(n) = T(n/2) + O(n)
• a = 1, b = 2, d = 1  a < bd • Hence, T(n) = O(n) • T(n) = 2T(n/2) + O(n) • a = 2, b = 2, d = 1  a = bd • Hence, T(n) = O(n log(n)) 21 Example • T(n) = 4T(n/2) + O(1) • a = 4, b = 2, d = 0  a > bd • Hence, T(n) = O(n2)
• T(n) = 3T(n/2) + O(1)
• a = 3, b = 2, d = 0  a > bd
• Hence, T(n) = O(nlog(3))  O(n1.6)
• T(n) = 4T(n/2) + O(n)
• a = 4, b = 2, d = 1  a > bd • Hence, T(n) = O(n2)
• T(n) = 3T(n/2) + O(n)
• a = 3, b = 2, d = 1  a > bd
• Hence, T(n) = O(nlog(3))  O(n1.6)
• (Karatsuba Multiplication) 22

Example 4
• What is the running time T(n) of the following procedure?
• If n > 0,
• T(n) = T(n – 1) + 1
• Else
• T(n) = 1
• Hence, T(n) = O(n)
public void method(int n) { c();
}
if (n > 0) method(n-1);
23

Example 5
• What is the running time T(n) of the following procedure?
• If n > 0,
• T(n) = T(n/2) + 1
• Else
• T(n) = 1
• Hence, T(n) = O(log(n))
public void method(int n) { c();
}
if (n > 0) method(n/2);
24

Example 6
• What is the running time T(n) of the following procedure?
• If n > 0,
• T(n) = 2T(n/2) + 1
• Else
• T(n) = 1
• Hence, T(n) = O(n)
public void method(int n) { c();
}
if (n > 0) { method(n/2); method(n/2);}
25

Proof of the
• We’ll do the same recursion tree thing we did for multiplication, but be more careful.
• Suppose that T(n) = aT(n/b) + cnd
• The hypothesis of the Master Theorem was the extra work at each
level was O(nd)
• That’s NOT the same as work  cnd for some constant c
• That’s true … we’ll actually prove a weaker statement that uses this hypothesis instead of the hypothesis that T(n) = aT(n/b) + O(nd)
Master
T
heorem
26

T(n) = aT(n/b) + cnd 1 problem of size n
a problems of size n/b a2 problems of size n/b2
…………
at problems of size n/bt …………
Level
# Problems
Size of each problem
Amount of work at this level
0
1
n
cnd
1
a
n/b
ac(n/b)d
2
a2
n/b2
a2c(n/b2)d
……
……
……
……
t
at
n/bt
atc(n/bt)d
……
……
……
……
logb(n)
alogb(n)
1
alogb(n) c
alogb(n) problems of size 1
27

Level
# Problems
Size of each problem
Amount of work at this level
0
1
n
cnd ac(n/b)d a2c(n/b2)d …… atc(n/bt)d
…… alogb(n) c
1
a
n/b
2
a2
n/b2
……
……
……
t
at
n/bt
……
……
……
logb(n)
alogb(n)
1
Total Work = 𝑐 ⋅ 𝑛𝑑 ⋅
𝑡 𝑡=0 𝑏𝑑
σlog𝑏(𝑛) 𝑎
28

Closer Look at All the Cases
• Total Work = 𝑐 ⋅ 𝑛𝑑 ⋅ σlog𝑏(𝑛) 𝑎 𝑡, 𝑡=0 𝑏𝑑
• where σlog𝑏(𝑛) 𝑎 𝑡 is a sum of geometric sequence 𝑡=0 𝑏𝑑
•If𝑎 𝑏𝑑
•If𝑎 𝑏𝑑
•If𝑎 𝑏𝑑
= 1, then T(n) = 𝑐 ⋅ 𝑛𝑑 ⋅ σlog𝑏(𝑛)
𝑡=0 𝑏𝑑
𝑎 𝑡= O(nd log(n))
𝑎 𝑡= O(nd)
< 1, then T(n) = 𝑐 ⋅ 𝑛𝑑 ⋅ σlog𝑏(𝑛) 𝑡=0 𝑏𝑑 𝑎 𝑡= O(nlogb(a)) 𝑡=0 𝑏𝑑 > 1, then T(n) = 𝑐 ⋅ 𝑛𝑑 ⋅ σlog𝑏(𝑛)
30

The eternal struggle
• Branching causes the number of problems to explode! • The most work is at the bottom of the tree!
• The problems lower in the tree are smaller! • The most work is at the top of the tree!
31

Consider Three Different Cases
(Case 1) T(n) = 2T(n/2) + O(n) • a = 2, b = 2, d = 1  a = bd
(Case 2) T(n) = T(n/2) + O(n)
• a = 1, b = 2, d = 1  a < bd (Case 3) T(n) = 4T(n/2) + O(n) • a = 4, b = 2, d = 1  a > bd
32

Consider Three Different Cases
(Case 1) T(n) = 2T(n/2) + O(n) • a = 2, b = 2, d = 1  a = bd
• The branching just balances out the amount of work
• The same amount of work is done at every level
• T(n) = (number of levels)(work per level) = log(n)  O(n) = O(n log(n))
1 problem of size n
2 problems of size n/2
4 problems of size n/4 …………
at problems of size n/at …………
n problems of size 1
33

Consider Three Different Cases
(Case 2) T(n) = T(n/2) + O(n)
• a = 1, b = 2, d = 1  a < bd • The amount of work done at the top (the biggest problem) swamps the amount of work done anywhere else • T(n) = T(work at top) = O(n) 1 problem of size n 1 problems of size n/2 1 problems of size n/4 ............ 1 problems of size n/2t ............ 1 problems of size 1 34 Consider Three Different Cases (Case 3) T(n) = 4T(n/2) + O(n) • a = 4, b = 2, d = 1  a > bd
• There are a HUGE number of leaves, and the total work is dominated by the time to do work at these leaves
• T(n) = O(work at bottom) = O( 4depth of tree ) = O(n2)
1 problem of size n 4 problems of size n/2
42 problems of size n/4 …………
4t problems of size n/2t …………
4depth of tree problems of size 1
35

Exercise
• Which is one of the following is the fastest and the slowest?
A. T(n) = T(n/2) + O(1)
B. T(n) = 5 T(n/6) + O(n)
C. T(n) = 2 T(n/3) + O(1)
D. T(n) = 10 T(n/30) + O(n1.1)
E. T(n) = T(0.5n) + O(n2)
F. T(n) = T(n-1) + T(n-2) + O(1)
36

Summary
• Asymptotic Analysis: Big-O, Big-Ω, Big-Θ • The ”Master Theorem” is a powerful tool
• It is a systematic approach to calculate general recurrence relations from scratch
• The master theorem applies to recurrence form: T(n) = aT(n/b) + O(nd),
where a  1, b > 1
• a: number of subproblems
• b: factor by which input size shrinks
• d: need to do nd work to create all the subproblems and combine their solution
• Case 1: If a = bd, then T(n) = O(nd log(n))
• Case 2: If a < bd, thenT(n) = O(nd) • Case 3: If a > bd, then T(n) = O(nlogb(a))
37

Related Posts