CS61B Lecture #16: Complexity
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 1
What Are the Questions?
Copyright By PowCoder代写 加微信 powcoder
• Cost is a principal concern throughout engineering:
“An engineer is someone who can do for a dime what any fool
can do for a dollar.” • Cost can mean
Operational cost (for programs, time to run, space requirements). Development costs: How much engineering time? When deliv-
Maintenance costs: Upgrades, bug fixes. Costs of failure: How robust? How safe?
this program fast enough? Depends on: For what purpose;
– Again depends on what input data. • How will it scale, as input gets big?
For what input data.
• How much space (memory, disk space)?
Last modified: Thu Feb 27 23:10:03 2020
CS61B: Lecture #16 2
Enlightening Example
Problem: Scan a text corpus (say 108 bytes or so), and find and print the 20 most frequently used words, together with counts of how often they occur.
• Solution 1 (Knuth): Heavy-Duty data structures
– Hash Trie implementation, randomized placement, pointers ga-
lore, several pages long.
• Solution 2 (Doug McIlroy): UNIX shell script:
tr -c -s ’[:alpha:]’ ’[\n*]’ < FILE | \ sort | \
uniq -c | \
sort -n -r -k 1,1 | \
• Which is better?
– #1 is much faster,
– but #2 took 5 minutes to write and processes 100MB in ≈ 50 sec. – I pick #2.
• In very many cases, almost anything will do: Keep It Simple.
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 3
Cost Measures (Time)
• Wall-clock or execution time
– You can do this at home:
time java FindPrimes 1000
– Advantages: easy to measure, meaning is obvious.
– Appropriate where time is critical (real-time systems, e.g.).
– Disadvantages: applies only to specific data set, compiler, ma- chine, etc.
• Dynamic statement counts of # of times statements are executed:
– Advantages: more general (not sensitive to speed of machine).
– Disadvantages: doesn’t tell you actual time, still applies only to specific data sets.
• Symbolic execution times:
– That is, formulas for execution times as functions of input size.
– Advantages: applies to all inputs, makes scaling clear.
– Disadvantage: practical formula must be approximate, may tell very little about actual time.
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 4
Asymptotic Cost
• Symbolic execution time lets us see shape of the cost function.
• Since we are approximating anyway, pointless to be precise about
certain things:
– Behavior on small inputs:
∗ Can always pre-calculate some results.
∗ Times for small inputs not usually important.
∗ Often more interested in asymptotic behavior as input size becomes very large.
– Constant factors (as in “off by factor of 2”):
∗ Just changing machines causes constant-factor change.
• How to abstract away from (i.e., ignore) these things?
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 5
Handy Tool: Order Notation
• Idea: Don’t try to produce specific functions that specify size, but rather families of functions with similarly behaved magnitudes.
• Then say something like “f is bounded by g if it is in g’s family.”
• For any function g(x), the functions 2g(x), 0.5g(x), or for any K > 0,
K · g(x), all have the same “shape”. So put all of them into g’s family.
• Any function h(x) such that h(x) = K · g(x) for x > M (for some constant M) has g’s shape “except for small values.” So put all of these in g’s family.
• For upper limits, throw in all functions whose absolute value is ev- erywhere ≤ some member of g’s family. Call this set O(g) or O(g(n)).
• Or, for lower limits, throw in all functions whose absolute value is everywhere ≥ some member of g’s family. Call this set Ω(g).
• Finally, define Θ(g) = O(g) ∩ Ω(g)—the set of functions bracketed in magnitude by two members of g’s family.
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 6
• Goal: Specify bounding from above. M=1
2g(x) f (x)
• Here, f(x) ≤ 2g(x) as long as x > 1,
• So f(x) is in g’s “bounded-above family,” written
f(x) ∈ O(g(x)),
• . . . even though (in this case) f (x) > g(x) everywhere.
Last modified: Thu Feb 27 23:10:03 2020
CS61B: Lecture #16 7
• Goal: Specify bounding from below: M=1
g(x) f′(x)
• Here, f′(x) ≥ 1g(x) as long as x > 1, 2
• So f′(x) is in g’s “bounded-below family,” written f′(x) ∈ Ω(g(x)),
• . . . even though f (x) < g(x) everywhere. Last modified: Thu Feb 27 23:10:03 2020
CS61B: Lecture #16 8
• In the two previous slides, we not only have f(x) ∈ O(g(x)) and f ′(x) ∈ Ω(g(x)),. . .
• . . . but also f(x) ∈ Ω(g(x)) and f′(x) ∈ O(g(x)).
• We can summarize this all by saying f(x) ∈ Θ(g(x)) and f′(x) ∈
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 9
Aside: Various Mathematical Pedantry
• Technically, if I am going to talk about O(·), Ω(·) and Θ(·) as sets of functions, I really should write, for example,
f ∈ O(g) instead of f(x) ∈ O(g(x))
• In effect, f(x) ∈ O(g(x)) is short for λ x. f(x) ∈ O(λ x. g(x)).
• The standard notation outside this course, in fact, is f(x) = O(g(x)), but personally, I think that’s a serious abuse of notation.
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 10
• For example,
which I would prefer to write
How We Use Order Notation
• Elsewhere in mathematics, you’ll see O(. . .), etc., used generally to specify bounds on functions.
π(N)=Θ( N ) lnN
π(N)∈Θ( N ) lnN
(Here, π(N) is the number of primes less than or equal to N.)
• Also, you’ll see things like
f(x)=x3 +x2 +O(x) (orf(x)∈x3 +x2 +O(x)), meaning that f(x) = x3 + x2 + g(x) where g(x) ∈ O(x).
• For our purposes, the functions we will be bounding will be cost func- tions: functions that measure the amount of execution time or the amount of space required by a program or algorithm.
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 11
Why It Matters
• Computer scientists often talk as if constant factors didn’t matter at all, only the difference of Θ(N) vs. Θ(N2).
• In reality they do matter, but at some point, constants always get swamped.
n16lgn√n n nlgn n2 n3 2n 2 16 1.4 2 2 4 8 4 4 32 2 4 8 16 64 16 8 48 2.8 8 24 64 512 256
16 64 4 16 64 256 4,096 65,636 32 80 5.7 32 160 1024 32,768 4.2×109 64 96 8 64 384 4,096 262,144 1.8×1019
128 112 11 128 896 16,384 2.1 × 109 3.4 × 1038 . . . . . . . .
1,024 160 32 1,024 10,240 1.0×106 1.1×109 1.8×10308 . . . . . . . .
220 320 1024 1.0 × 106 2.1 × 107 1.1 × 1012 1.2 × 1018 6.7 × 10315,652
• For example: replace column n2 with 106 · n2 and it still becomes
dominated by 2n.
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 12
Some Intuition on Meaning of Growth
• How big a problem can you solve in a given time?
• In the following table, left column shows time in microseconds to
solve a given problem as a function of problem size N.
• Entries show the size of problem that can be solved in a second, hour, month (31 days), and century, for various relationships be- tween time required and problem size.
• N = problem size. Time (μsec) for
problem size N
Possible in
1 hour 1 month 1 century
101000000000 108·1011 101014
N 106 3.6·109 2.7·1012 3.2·1015
N lg N 63000 1.3 · 108 7.4 · 1010 6.9 · 1013 N2 1000 60000 1.6·106 5.6·107 N3 100 1500 14000 150000
2N 20 32 41 51 Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 13
Using the Notation
• Can use this order notation for any kind of real-valued function.
• We will use them to describe cost functions. Example:
/** Find position of X in list L, or -1 if not found. */
int find(List L, Object X) { int c;
for (c = 0; L != null; L = L.next, c += 1) if (X.equals(L.head)) return c;
return -1; }
• Choose representative operation: number of .equals tests.
• If N is length of L, then loop does at most N tests: worst-case
time is N tests.
• In fact, total # of instructions executed is roughly proportional to N in the worst case, so can also say worst-case time is O(N), regardless of units used to measure.
• Use N > M provision (in defn. of O(·)) to ignore empty list.
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 14
Be Careful
• It’s also true that the worst-case time is O(N2), since N ∈ O(N2) also: Big-Oh bounds are loose.
• The worst-case time is Ω(N), since N ∈ Ω(N), but that does not mean that the loop always takes time N, or even K · N for some K.
• Instead, we are just saying something about the function that maps N into the largest possible time required to process any array of length N.
• To say as much as possible about our worst-case time, we should try to give a Θ bound: in this case, we can: Θ(N).
• But again, that still tells us nothing about best-case time, which happens when we find X at the beginning of the loop. Best-case time is Θ(1).
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 15
Effect of Nested Loops
• Nested loops often lead to polynomial bounds:
for (int i = 0; i < A.length; i += 1) for (int j = 0; j < A.length; j += 1)
if (i != j && A[i] == A[j])
return true;
return false;
• Clearly, time is O(N2), where N = A.length. Worst-case time is
• Loop is inefficient though:
for (int i = 0; i < A.length; i += 1)
for (int j = i+1; j < A.length; j += 1)
if (A[i] == A[j]) return true; return false;
• Now worst-case time is proportional to
N − 1 + N − 2 + . . . + 1 = N (N − 1)/2 ∈ Θ(N 2)
(so asymptotic time unchanged by the constant factor).
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 16
Recursion and Recurrences: Fast Growth
• Silly example of recursion. In the worst case, both recursive calls happen:
/** True iff X is a substring of S */
boolean occurs(String S, String X) {
if (S.equals(X)) return true;
if (S.length() <= X.length()) return false; return
occurs(S.substring(1), X) ||
occurs(S.substring(0, S.length()-1), X);
• Define C(N) to be the worst-case cost of occurs(S,X) for S of
length N , X of fixed size N0, measured in # of calls to occurs. Then C ( N ) = 1 , i f N ≤ N 0 ,
2 C ( N − 1 ) + 1 i f N > N 0
• So C(N) grows exponentially:
C(N) = 2C(N−1)+1=2(2C(N−2)+1)+1=…=2(···2·1+1)+…+1
= 2N−N0 +2N−N0−1 +2N−N0−2 +…+1=2N−N0+1 −1∈Θ(2N)
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 17
Binary Search: Slow Growth
/** True X iff is an element of S[L .. U]. Assumes
* S in ascending order, 0 <= L <= U-1 < S.length. */
boolean isIn(String X, String[] S, int L, int U) { if (L > U) return false;
int M = (L+U)/2;
int direct = X.compareTo(S[M]);
if (direct < 0) return isIn(X, S, L, M-1); else if (direct > 0) return isIn(X, S, M+1, U); else return true;
• Here, worst-case time, C(D), (as measured by # of calls to .compareTo),
depends on size D = U − L + 1.
• We eliminate S[M] from consideration each time and look at half the
rest. Assume D = 2k − 1 for simplicity, so:
0, ifD≤0, 1+C((D−1)/2), ifD>0.
1+1+…+1+0
k k=lg(D+1)∈Θ(lgD)
Last modified: Thu Feb 27 23:10:03 2020
CS61B: Lecture #16 18
Another Typical Pattern: Merge Sort
List sort(List L) {
if (L.length() < 2) return L;
Split L into L0 and L1 of about equal size;
L0 = sort(L0); L1 = sort(L1);
return Merge of L0 and L1 }
• Assuming that size of L is N = 2k, worst-case cost function, C(N), counting just merge time (which is proportional to # items merged):
C ( N ) = 0 , i f N < 2 ; 2 C ( N / 2 ) + N , i f N ≥ 2 .
= 2(2C(N/4) + N/2) + N
= 4C(N/4)+N +N
= 8C(N/8)+N +N +N
= N·0+N+N+...+N
• In general, can say it’s Θ(N lg N ) for arbitrary N (not just 2k ).
Merge (“combine into a single or-
dered list”) takes time proportional
to size of its result.
Last modified: Thu Feb 27 23:10:03 2020 CS61B: Lecture #16 19
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com