CMPS 12B Lecture 5: Class 5 - Sorting
Premium

4 Pages
20 Views
Unlock Document

Department
Computer Science
Course
CMPS 12B
Professor
Darrell Long
Semester
Spring

Description
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


OR

Join OneClass

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

Sign up

Join to view


OR

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.


Submit