CS代考 CS61B Lecture #16: Complexity

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