1- Logarithmic Algorithms:

This type is the fastest of those 4 classes. It has a run curve that looks something like this:

bool BSearch(int[] list, int item, int first, int last) { if(last - first < 2) return list[first] == item || list[last] == item; int mid = (first + last)/2; if(list[mid] == item) return true; if (list[mid] > item) return BSearch(list, item, first, mid - 1); return BSearch(list, item, mid + 1, last); }

2- Linear Algorithms:

Runs in time, linear to the input items. It's curve looks like the following:

A linear search is a typical example of that, where one would traverse the array or, whatever data structure, item by item. An implementation of linear search looks like this:

bool LinearSearch(int[] list, int item) { for(int i = 0; i < list.Length; i++) if(list[i] == item) return true; return false; }3- Quadratic Algorithm: This one runs time grows to to the power of 2, with each increase in the input sizes, which means while processing 2 items the algorithm will do 4 steps, 3 items will take 9 steps, 4 items will take 16 steps, etc. The next figure shows how a quadratic curve might look like:

A famous example of an algorithm with quadratic growth is Selection Sort:

void SelectionSrot(int[] list) { int i, j; int min, temp; for (i = 0; i < list.Length - 1; i++) { min = i; for (j = i + 1; j < list.Length; j++) { if (list[j] < list[min]) { min = j; } } temp = list[i]; list[i] = list[min]; list[min] = temp; } }

4- Exponential Algorithm:

This is the super slow of this list of four. It grows exponentially (that is, for 2 items it takes 2 ^ 2, for 3 items it takes 2^3, for 4 items it takes 2 ^ 4, etc.

Again algorithms are the key to computer science, the most fun part of programmer's job. Choose your algorithms carefully and always try to improve.

Hope this helps.

## 2 comments:

A more fine-grained and comprehensive listing:

http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities

Nice table, good link. Thank you!

Post a Comment