Transcript Document

Efficiency of Algorithms
Csci 107
Lecture 8
• Last time
– Data cleanup algorithms and analysis
– (1), (n), (n2)
• Today
– Binary search and analysis
– Order of magnitude (lg n)
– Sorting
• Selection sort
Searching
• Problem: find a target in a list of values
• Sequential search
– Best-case : (1) comparison
• target is found immediately
– Worst-case: (n) comparisons
• Target is not found, or is the last element in the list
– Average-case: (n) comparisons
• Target is found in the middle
• Can we do better?
– No…unless we have the input list in sorted order
Searching a sorted list
• Problem: find a target in a sorted list
– How can we exploit that the list is sorted, and come up
with an algorithm faster than sequential search in the
worst case?
– How do we search in a phone book?
– Can we come up with an algorithm?
• Check the middle value
• If smaller than target, go right
• Otherwise go left
Binary search
•
•
•
•
Get values for list, A1, A2, ….An, n , target
Set start =1, set end = n
Set found = NO
Repeat until ??
– Set m = middle value between start and end
– If target = m then
• Print target found at position m
• Set found = YES
– If target < Am then
• end = m-1
– Else
• start = m+1
• If found = NO then print “Not found”
• End
Efficiency of binary search
• What is the best case?
– Found in the middle
• What is the worst case?
– Initially the size of the list is n
– After the first iteration through the repeat loop, if not found, then
either start = middle or end = middle ==> size of the list on which
we search is n/2
– Every time in the repeat loop the size of the list is halved: n, n/2,
n/4,….
– How many times can a number be halved before it reaches 1?
log2 x
• log2 x
– The number of times you can half a (positive)
number x before it goes below 1
– Examples:
• log2 16 = 4 [16/2=8, 8/2=4, 4/2=2, 2/2=1]
• log2 n = m <==> 2m = n
• log2 8 = 3 <==> 23=8
log2 x
Increases very slowly
• log2 8 = 3
• log2 32 = 5
• log2 128 = 7
• log2 1024 = 10
• log2 1000000 = 20
• log2 1000000000 = 30
• …
Orders of magnitude
• Order of magnitude ( lg n)
– Worst-case efficiency of binary search: ( lg n)
• Comparing order of magnitudes
(1) << (lg n) << (n) << (n2)
Comparing (lg n) and (n)
Does efficiency matter?
• Say n = 109 (1 billion elements)
• 10 MHz computer ==> 1 instr takes 10-7 sec
– Seq search would take
• (n) = 109 x 10-7 sec = 100 sec
– Binary search would take
• (lg n) = lg 109 x 10-7 sec = 30 x10-7 sec = 3 microsec
Sorting
• Problem: sort a list of items into alphabetical or
numerical order
• Why sorting?
– Sorting is ubiquitous (very common)!!
– Examples:
• Registrar: Sort students by name or by id or by department
• Post Office: Sort mail by address
• Bank: Sort transactions by time or customer name or accound
number …
• For simplicity, assume input is a list of n numbers
• Ideas for sorting?
Selection Sort
• Idea: grow a sorted subsection of the list from the back to
the front
57216483|
5721643|8
521643|78
52134|678
…
|1 2 3 4 5 6 7 8
Selection Sort
• Pseudocode (at a high level of abstraction)
– Get values for n and the list of n items
– Set marker for the unsorted section at the end of the list
– Repeat until unsorted section is empty
• Select the largest number in the unsorted section of the list
• Exchange this number with the last number in unsorted section of list
• Move the marker of the unsorted section forward one position
– End
Selection Sort
• Level of abstraction
– It is easier to start thinking of a problem at a high level
of abstraction
• Algorithms as building blocks
– We can build an algorithm from “parts” consisting of
previous algorithms
– Selection sort:
• Select largest number in the unsorted section of the list
• We have seen an algorithm to do this last time
• Exchange 2 values
Selection Sort Analysis
• Iteration 1:
– Find largest value in a list of n numbers : n-1 comparisons
– Exchange values and move marker
• Iteration 2:
– Find largest value in a list of n-1 numbers: n-2 comparisons
– Exchange values and move marker
• Iteration 3:
– Find largest value in a list of n-2 numbers: n-3 comparisons
– Exchange values and move marker
• …
• Iteration n:
– Find largest value in a list of 1 numbers: 0 comparisons
– Exchange values and move marker
Total: (n-1) + (n-2) + …. + 2 + 1
Selection Sort
• Total work (nb of comparisons):
– (n-1) + (n-2) + …. + 2 + 1
– This sum is equal to .5n2 -.5n (proved by Gauss)
=> order of magnitude is ( ? )
• Questions
– best-case, worst-case ?
– we ignored constants, and counted only comparisons.. Does this
make a difference?
• Space efficiency
– extra space ?
Selection Sort
• In conclusion: Selection sort
– Space efficiency:
• No extra space used (except for a few variables)
– Time efficiency
• There is no best-case and worst-case
• the amount of work is the same: (n2) irrespective of
the input
• Other sorting algorithms? Can we find more
efficient sorting algorithms?
Exam 1
• Wednesday: Lab 4 (more efficiency, binary search, etc)
– Due next Wednesday, but…
– Strongly encouraged to finish lab before Exam1
• Exam 1 (Monday febr 21st)
–
–
–
–
Material: Algorithms and efficiency
Open books, notes, labs
Practice problems handout
Study group: this time only, Sunday night (instead of Monday)
• Tom will email