This article is geared towards the sort of complexity analysis you may be asked to do in interviews, so it is fairly superficial, but should also be accurate. Complexity theory is, of course, a vast field of its own, but in practice, most software engineers use only a small part day to day. What an engineer needs to know is how expensive an algorithm is. Understanding complexity lets you critique and revise algorithms in a sensible manner, a particularly useful skill for programmers.
Fortunately, you can learn all you really need to know about basic analysis in a few minutes.
Complexity is expressed in relation to the size of input. For sake of argument, let's consider set of input data such as A = { } and B = { 1, 2, 3 }. When we're talking about input as a variable (could be A, B, or whatever) then we'll call it X.
Time Complexity by Example
Constant Time: Algorithm a: O(1)
a(X) = { return 199; }a(A) = 199;
a(B) = 199;
This is just shorthand. In other words, algorithm a(X) always returns 199.
Algorithm a, given input X, always does the same amount of work. The expense of the algorithm - how much time and space it requires to work - is constant and invariant. It does not vary according to the size of the input. This is expressed in Big O notation as O(1).
Time complexity of a(X) = O(1).
In fact, anything done the same number of times regardless of the size of the input takes constant time. Let's consider algorithm a1:
a1(X) = { k = compute 200 trillionth digit of pi; return k; }
This is an example of a time-consuming calculation. Despite its impracticality, it doesn't vary according to the size of the input so it's constant time. (A hint here is that X is never referenced in the function, but it's possible to reference X and still have constant time; maybe covered later.)
Time complexity of a1(X) = O(1).
Linear Time: Algorithm b: O(n)
b(X) = { for each element of X, add the element value to variable k; return k; }In other words, b(X) adds up every element of X and returns the total.
b(A) = 0;
b(B) = 6;
Etc.
Let's look at the expense of running the algorithm; how much effort the machine running the algorithm goes through to finish the algorithm's calculations. We can express this in steps.
For set A, algorithm b does nothing. "For each element" occurs zero times because there are zero input elements. Steps = 0.
For set B, algorithm b takes three steps. "For each element" occurs once for each element in the input. Since there are three elements in the input, there are three steps. To be terribly pedantic, here's more detail:
Step 1: add X[0] to k
Step 2: add X[1] to k
Step 3: add X[2] to k
It's easy to see that algorithm b takes one step for every element in its input. This is a direct, linear relationship. We call it linear time. Expressed in Big O notation, this is O(n), "n" being the number of elements in the input. In our examples, n(A) = 0, and n(B) = 3.
Time complexity of b(X) = O(n).
Of course, this isn't all that algorithm b does. Algorithm b also does these things:
Step 0: create variable k and set it to 0
Step 4: return k
Crucially, algorithm b always does these things, invariant to the number of elements in its input. As a result, these steps are done in constant time, and if an algorithm is more complex than constant time in any way, we disregard its constant time elements. We could say that the time complexity of b = O(n) + O(1), but in practice we don't. This reminds me of the +C result in integrals.
Sometimes an algorithm has a chance of stopping early. For example, Algorithm b1:
b1(X,j) = {for each element of X, if its value equals j, return its position k; }
In other words, look though the input until you find j, and then return its position.
Consider b1(B,j). With j = 1, the algorithm takes one step. With j = 3, algorithm b1 takes three steps.
Even in the case of an algorithm short-circuiting right away, we actually consider complexity in the worst case scenario. You must ask yourself the question, "What could possibly go wrong?" And then make the assumption it will take as many steps as it possibly could. It's pessimism for fun and profit.
Time complexity of b1(X) = O(n).
Quadratic Time: Algorithm c: O(n^m)
c(X) = { for each element of X, add the value of every other element to variable k; return k; }A high level statement of an algorithm can hide the details of the approach; since an algorithm is an exact set of instructions, not the idea of a set of instructions, here’s enough detail for us to work with:
c(X) =
For each element e1 in X,
For each element e2 in X, except element e2,
Add e2 to j
Add j to k
Return k;
c(A) = 0;
c(B) = 12;
For input set B, these are the steps taken:
Step 1: add X[1] to j
Step 2: add X[2] to j
Step 3: add j to k
Step 4: add X[0] to j
Step 5: add X[2] to j
Step 6: add j to k
Step 7: add X[0] to j
Step 8: add X[1] to j
Step 9: add j to k
It is of course no coincidence that there are 9 steps, 3 elements in B, and 3^2 = 9. Since we're vising each element as many times are there are elements, the number of steps is n times n, or n^2.
Time complexity of c(X) = O(n^2).
Algorithms a, b, and c indicate that one rule of thumb for finding complexity is to look at the loops. Each nested loop (over all elements) increases the exponent of time complexity by one.
No loops = n^0
1 loop = n^1
2 nested loops = n^2
m nested loops = n^m
Logarithmic Time: Algorithm d: O(log(n))
d(X,j) = { search ordered input X for element value j and return its position k; }Our implementation of algorithm d will be a binary search. This search probes input X at diminishing intervals to isolate the position element value j must be. In this case we are executing a loop, but not over all elements of the input (for sizeable inputs, anyway).
Quick summary of binary search: check the value of the middle element k of the input set. If it is equal to the target value j, return k. If it is less than j, repeat this operation with the set of input from k to the end of the input. If it is greater than j, repeat this operation with the set of inputs from the start of the input to k. If the set of inputs is at any time empty, return error value (j not found).
The number of probes to either find j or determine that j is not in the input X is the base 2 logarithm of n, the number of elements in input X.
Time complexity of d(X,j) = O(log(n))
While there is a loop in this algorithm, we do not visit each element to complete the loop. For temporal complexity this loop counts as log(n) Within a set of nested loops it counts for less than n; for example, an algorithm that does a binary search, but at each probe loops through the entire input X, has a time complexity O(log(n) x n). This is often written (O)(n log(n)).
Linear Time Part 2: Algorithm e: O(n+m)
e(X,Y) = { add the sum of every element of X to the sum of every element of Y; return sum k; }This can be implemented in terms of algorithm b, which sums input.
e(X,Y) = { k = b(X) + b(Y); return k; }
The complexity of this algorithm is best expressed in terms of both X and Y. In standard notation it would be O(n+ m), where n = the number of elements in X and m = the number of elements in Y. This is still considered linear time.
Time complexity of e(X,Y) = O(n+m)
Once you start passing functions as arguments, you can compound complexities for fun and profit.
Exponential and Factorial Time: O(2^n), O(n!)
Many other exciting complexity types exist, of course.…And that should pretty much get you through interviews and day to day life.
No comments:
Post a Comment