The solution is often a matter of visualization. Dry, boring problems become quite entertaining when you can see and touch the problem. For example, have you ever seen Jonathan Harris' Universe? If you haven't, you should. It will completely change your perception of search.
I'm going to tackle an example from my own recent experience. When you take a typical analysis / algorithms course, you spend a good deal time learning some basic mathematical techniques for gauging the efficiency of your algorithms. CS guys refer to it as "big-O", "big-Omega" and "big-Theta" analysis. There are corresponding "little" versions of these functions.
Big-O is what we care about the most. It helps to figure out how many operations your algorithm executes relative to the size of your data. In other words, for every piece of data, do you only need to look at that element one time or do you need to look at it a number of times equal to the size of your data (n^2) and so on.
So as a student you spend a lot of time analyzing well known operations. Searching, sorting and string matching are typical suspects. It is useful to know which is more efficient, merge sort or insertion sort. How else would you decide which to choose?
Still, the analysis can be very monotonous, tedious and just plain boring. Let's try to visualize it to appreciate it more. I wrote some quick merge and insertion sort code to illustrate the point more visually.
1: //-- insertion sort code snippet
2: unsigned long insertion_sort(int array[], int n) {
3: int tmp;
4: unsigned long count = 0;
5: // for each element compare backwards until it matches
6: for (int i = 1; i < n; i++) {
7: tmp = array[i];
8: count++;
9: // count backwards,, shifting until done shifting.
10: for (int j = i - 1; j >= 0; j--) {
11: count++;
12: if (array[j] <= tmp) {
13: array[j + 1] = tmp;
14: count++;
15: break;
16: }
17: array[j + 1] = array[j];
18: count++;
19: count++;
20: if (j == 0) {
21: array[j] = tmp;
22: count++;
23: break;
24: }
25: }
26: }
27: return count;
28: }
29: //-- merge sort code snippet
30: unsigned long merge(int * left, int llen, int * right, int rlen) {
31: unsigned long count = 0;
32: int totalLength = llen + rlen;
33: int * result = (int * ) malloc(sizeof(int) * (rlen + llen));
34: int * resptr = result;
35: int * lptr = left;
36: int * rptr = right;
37: // while there are remaining numbers in left and right, pick the smallest
38: // number to append to result.
39: while (llen > 0 && rlen > 0) {
40: count++;
41: if ( * lptr <= * rptr) { * resptr = * lptr;
42: lptr++;
43: llen--;
44: resptr++;
45: } else { * resptr = * rptr;
46: rlen--;
47: rptr++;
48: resptr++;
49: }
50: }
51: // now append the leftover data to the result array
52: // is left the side with data left?
53: while (llen > 0) {
54: count++; * resptr = * lptr;
55: lptr++;
56: llen--;
57: resptr++;
58: }
59: // is right the side with data left?
60: while (rlen > 0) {
61: count++;; * resptr = * rptr;
62: rlen--;
63: rptr++;
64: resptr++;
65: }
66: count++;
67: memcpy(left, result, sizeof(int) * totalLength);
68: free(result);
69: return count;
70: }
71: unsigned long merge_sort(int * array, int len) {
72: unsigned long count = 0;
73: if (len <= 1) {
74: return count;
75: }
76: // divide the array in half, merge sort each side, then merge the sides
77: int middle = len / 2;
78: count++;
79: count += merge_sort(array, middle);
80: count += merge_sort(array + middle, len - middle);
81: count += merge(array, middle, array + middle, len - middle);
82: return count;
83: }
I wrote a quick driver to run each algorithm on the same set of data 20 times with ever increasing numbers of integers. Here are the graphs of the results:
Now the line appears jagged of course, but that's fine. You should view this from a statistical point of view and consider what the best fit line would look like. It looks like a smooth x^2 parabola.
The green lines here are not to scale with the axis labels, it's there to illustrate the constant difference between what the code calculated and what theory stipulates. A constant difference is what you should expect, the growth pattern is what we're interested in here. Remember, don't let the relative scales of these graphs fool you, review the first graph again to see how quickly these functions diverge and look at the scale of the y axis on the function graphs.
So it's one thing to know that merge sort is n^2/lg(n) times faster than insertion sort. Seeing it is something else. So let's them graph all together.
This provides a pretty convincing illustration. You can keep graphs like this in mind when writing your nested loops, when working with null terminated string where the compiler has to iterate over its length frequently, and just in the generality of reducing complexity and how much it can actually be worth.
