The first step in learning how to categorize—and then build—efficient code is learning the basic patterns we covered in the first article on complexity:
- a number of steps that doesn’t change with respect to the input size is constant complexity—like accessing some spot in memory
- a number of steps that’s proportional to the log of the input size is logarithmic complexity—like binary search
- a number of steps that’s proportional to the input size is linear complexity—like linear search (this is why it has that name)
- a number of steps that’s proportional to some power of the input size is quadratic complexity—like anything with a loop inside a loop inside a loop inside a loop …
- etc.
Each complexity class has some recognizable patterns, that, at a glance, tell you the complexity of some code.
This, for example, has quadratic complexity:
public boolean findDuplicates(int[] inputData) {
for (int i = 0; i < inputData.length; i++) {
for (int j = 0; j < inputData.length; j++) {
if (inputData[i] == inputData[j] && i != j) {
return true;
}
}
}
return false;
}
For every i, for every j (in other words i*j times), we do a thing.
Now, let’s look at this code:
public class NLogNLoopDemo {
public static void main(String[] args) {
int n = 16; // You can change this value to see how it scales
int count = 0;
for (int i = 0; i < n; i++) { // O(n)
for (int j = 1; j < n; j = j * 2) { // O(log n)
System.out.println("i = " + i + ", j = " + j);
count++;
}
}
System.out.println("Total iterations: " + count);
}
}
For every i, for a small subset of the j’s (those that are double as far away as the previous j—which does not mean “half the j’s”), we do a thing. This setup is nlogn.
What I want to talk about now assumes you’re comfortable looking at code and seeing these patterns—so you know MergeSort is in nlogn, or looping through an array once is n—but how we take these classifications and make decisions based on them.
Recall the case of BubbleSort. Because of how the bubbling mechanism works, the best scenario is when the array is already sorted—and then the algorithm just does one pass in linear time to check that that’s the case.
But the worst case is that the array is already sorted, but in the opposite order. In that case, the algorithm does n-1 swaps to get the first number in place, then n-2, then n-3, then n-4…; and the whole sum of these numbers is proportional to n^2, so in the worst case, BubbleSort is n^2.
On average, we’ll fall somewhere in the middle. With randomized numbers, some will be sorted, and some won’t be sorted. The average of n and n^2 is (n+n^2)/2, which we actually consider to be n^2. This is because of two reasons already alluded to in our first discussion
- n^2 dominates n, so taking a shortcut and calling “n^2+n”, as things go to their limits, is perfectly acceptable
- We ignore constants. 2n^2 looks the same (except for a stretch) compared to n^2; we only say that functions are “different” if they really are, like n^2 and n!.
In computer science, we often do three kinds of analysis on an algorithm (for time and/or space, so, I guess, six types):
- If everything is as easy as possible for the algorithm, what’s the best-case scenario for its performance?
- If everything is how we expect it to be on average, what’s the average-case scenario for its performance?
- If everything is as hard as possible for the algorithm, what’s the worst-case scenario for its performance?
Most of the time, however, when designing software, you care much more about the worst-cases than the best.
For each of these, we have 3 possible classes they could fit into: Omega (Ω), Theta (Θ), and Big-O (denoted with the familiar Latin-alphabet “O”, as in “the letter before P,” not a 0):
If an algorithm’s cost function is Big-Omega of a certain class of functions, then it means there is some constant C, such that for C times the class is always less than the cost function. That is, the cost function always performs worse than the constant-times-class, and constant-times-class is therefore a lower bound.
If an algorithm’s cost function is Big-Omega of a certain class of functions, then it means there is some constant C, such that for C times the class is always less than the cost function. That is, the cost function always performs worse than the constant-times-class, and constant-times-class is therefore a lower bound. You will not do any better than this lower bound.
If an algorithm’s cost function is Big-O of a certain class of functions, then it means there is some constant C, such that for C times the class is always greater than the cost function. That is, the cost function always performs better than the constant-times-class, and constant-times-class is therefore an upper bound. You will not do any worse than this lower bound.
If an algorithm is both Big-O and Big-Omega of some cost function class, then you have enough evidence to state that it’s Big-Theta of that class.
We need to draw an important distinction between best/worst/average and Omega/Theta/O: For each of the cases (best/worst/average), you can perform Omega/Theta/O analysis. Omega is not the exclusive domain of the best case (which can have its own big-O and potentially big-Theta), and O is not the exclusive domain of the worst case (which can have its own big-Omega and potentially big-Theta). It is perfectly fine to say that “the worst case scenario of [some code] is ‘big-Omega of n^2’” or that “the average case is ‘big-O of nlogn’”
No comments:
Post a Comment