* 12.7(a,c).
Reading Assignments
* Ch 10 (very useful for your current homework.)
Assignment #5
* You may want to interact with fellow students or consultants to share ideas or thoughts before you start programming.
* due Fri, Aug 4.
Time complexity of recursive functions
void mystery1(int x)
{
for (int i = 1; i <= x; i++) {
// some task requiring constant time
}
if (x > 1) {
mystery1(x - 1);
}
}
long fib(int n)
{
if (n < 0) {
// error
} else if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else { return fib(n - 1) + fib(n - 2);
}
}
Selection Sort
void sort(int v[], int n)
{
for (int bottom = n - 1; bottom >= 1; bottom--) {
int max_index = 0; for (int i = 1; i <= bottom; i++) {
if (v[i] > v[max_index]) {
max_index = i;
}
}
swap(v[bottom], v[max_index]);
}
}
void swap(int& x, int& y)
{
int temp = x; x = y; y = temp;
}
Bubble sort
// just the algorithm is shown
for (int bottom = n - 1; bottom > 0; bottom--) {
for (int i = 0; i < bottom; i++) {
if (v[i] > v[i+1]) {
swap(v[i], v[i+1]);
}
}
}
* number of comparisons = O(n2) for both
* number of swaps = O(n) for selection sort, O(n2) for bubble sort.
Quick sort
void qsort(int v[], int lower, int upper)
{
// zero or one item to sort
if (lower >= upper) {
return;
}
// two items to sort
if (upper - lower == 1) {
if (v[lower] > v[upper]) {
swap(v[lower], v[upper]);
}
return;
}
// three or more items to sort
int mid = (lower + upper) / 2;
int pivot = v[mid];
swap(v[mid], v[lower]);
int lo = lower + 1;
int hi = upper;
do {
while ((lo <= hi) && v[lo] <= pivot) {
lo++;
}
while (v[hi] > pivot) { hi--; }
if (lo < hi) {
swap(v[lo], v[hi]);
}
} while (lo < hi); v[lower] = v[hi];
v[hi] = pivot;
qsort(v, lower, hi-1);
qsort(v, hi+1, upper);
}
* Worst case: O(N2)
* Average case: O(N log N)
Cautions about Big-O analysis
* Limitations
1. For complicated algorithms, big-O analysis may be extremely difficult or impossible.
2. Big-O is a coarse measure that cannot capture small differences in algorithms.
f(n) = 1000 n (seconds)
g(n) = 0.001 n (seconds)
Both are O(n) but 1 is 1 million times faster!
h(n) = 0.000001 n5 + 1000 n4
O(n5) if n > 1,000,000,000 !
O(n4) may be a more reasonable measure.
3. Big-O says little or nothing about algorithm for small sets of data.