ANALYSIS OF ALGORITHMS
‣ observations
‣ mathematical models
‣ order-of-growth classifications
‣ theory of algorithms
‣ memory
Programmer needs to develop
a working solution.
Client wants to solve
problem efficiently.
Theoretician wants
to understand.
Basic blocking and tackling
is sometimes necessary.
Student might play
any or all of these
roles someday in yellow color.
‣ Observations
Example: 3-SUM
Given N distinct integers, how many triples sum to exactly zero?
Input=> 8
30 -40 -20 -10 40 0 10 5
Output=> 4
3-SUM: brute-force algorithm
public class ThreeSum
{
public static int count(int[] a)
{
int N = a.length;
int count = 0;
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < N; k++) ------> check each triple
if (a[i] + a[j] + a[k] == 0) ------> for simplicity, ignore
integer overflow
count++;
return count;
}
public static void main(String[] args)
{
int[] a = In.readInts(args[0]);
StdOut.println(count(a));
}
}
Common order-of-growth classifications
Binary search demo
Goal. Given a sorted array and a key, find index of the key in the array?
Binary search.
Compare key against middle entry.
・Too small, go left.
・Too big, go right.
・Equal, found.
public static int binarySearch(int[] a, int key)
{
int lo = 0,
hi = a.length-1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
Types of analyses
Best case. Lower bound on cost.
・Determined by “easiest” input.
・Provides a goal for all inputs.
Worst case. Upper bound on cost.
・Determined by “most difficult” input.
・Provides a guarantee for all inputs.
Average case. Expected cost for random input.
・Need a model for “random” input.
・Provides a way to predict performance.
Ex 1. Array accesses for brute-force 3-SUM.
Best: ~ ½ N 3
Average: ~ ½ N 3
Worst: ~ ½ N 3
Ex 2. Compares for binary search.
Best: ~ 1
Average: ~ lg N
Worst: ~ lg N
Goals.
・Establish “difficulty” of a problem.
・Develop “optimal” algorithms.
Approach.
・Suppress details in analysis: analyze “to within a constant factor”.
・Eliminate variability in input model by focusing on the worst case.
Optimal algorithm.
・Performance guarantee (to within a constant factor) for any input.
・No algorithm can provide a better performance guarantee.
Basics
Bit. 0 or 1.
Byte. 8 bits.
Megabyte (MB). 1 million or 220 bytes.
Gigabyte (GB). 1 billion or 230 bytes.
Typical memory usage for objects in JavaObject overhead. 16 bytes.
Reference. 8 bytes.
Padding. Each object uses a multiple of 8 bytes.
Ex 1. A Date object uses 32 bytes of memory.
public class Date
{ 16 bytes (object overhead)
private int day; 4 bytes (int)
private int month; 4 bytes (int)
private int year;
... 4 bytes (int)
} 4 bytes (padding)
32 Bytes(total)
This is dummy text. It is not meant to be read. Accordingly, it is difficult to figure out when to end it. But then, this is dummy text. It is not meant to be read. Period.
ConversionConversion EmoticonEmoticon