CMPS 12B Lecture 5: Class 5 - Sorting

4 Pages
Unlock Document

Computer Science
Darrell Long

CMPS 12B Lecture 5 4/18/2017 (3:20-4:55) Announcements Trying overhead instead of chalkboard Sorting • How fast? o Big-O notation. o f + g o f is O(g) if 3 [3 = there exists] c, n(0) 3 o f(n) <= c*g(n) ^ n>n(0) ▪ n is bounded from above by g, upper bound o f is @(g) [@ = Omega] iff f is O(g) and g is 0(f) o log(n) O(n) ▪ log(10) 100 = 2 <= 100 o lim  of f(n)/g(n) = c – f is @(s) o lim  of log(n)/n = lim  of ln(V)log(e)/n = lim  (1/n)log€/1 = lim  1/n*log(e)= 0 • Ex: You have a list of N random numbers. o How fast can I do member(x, List)? for(int I = 0; I < len; i++) { if (List[i] == x) { return i; } return -1;  O(n) } • If we know X is in the list, then .5N • Idea 1: Sort it – O(nlog(n)) o Ex: Take set of 10 numbers; to find 7, you divide 10 by 2, then check to see if the number you’re looking for is larger. If so, search remaining upper half. o log(2)(n) is the amount of times you can divide the number by two. ▪ N = 2^(log(2)(N)) ▪ O(logN)  Optimal o If list is sorted, you can find something in logarithmic time Binary Search i = first; j = last; while (i <= j) { k = (I + j)/2; if x = a[k] then found else if (x < a[k]) then j = k - 1 else if (x > a[k]) then i = k+1 return not found Importance of Optimizing Your Program • Done in Mathematica Program • Intractable – too hard to compute • n! = Brute force search (Permutations - slowest) Back to n! • n! = n(n-1)! = n(n-1)(n-2)! = n(n-1)…0! = O(n) There are n operations • f(k) = f(k-2) + f(k-1)
More Less

Related notes for CMPS 12B

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.