I've been programming for many years, but I've just realized that I don't pay too much attention on the performance and efficiency of my code. For my past projects, I've only know to care about what I can produce and not how well I can make it work. The main reason for this is because my knowledge is so limited; therefore, I need some improvements. I don't want to be just another programmer, but I want to be a good programmer; writing effective and efficient code.
Direct accessing and storing contents- suboptimal when (large) data needs to be searched
Array- searching an unsorted array process takes time proportional to the number of elements in the array
List
These collections only allo data to be accessed in a predetermined order
Queue
Stack
Hashtables - direct access, but store data indexed by an arbitray object (such as string key)
Logarithmically proportional to the number of elements log(n)
Binary Search Tree - improve efficiency for serach
SkipLists - mixed between binary trees and linked lists
*********************************************************
Graph - a collection of nodes with a set of edges connecting the various nodes.
Set - an unordered collection of items
Disjoint sets - collection of sets that have no elements incommon with one another
The time it takes to search an array is linearly proportional to the number of elements in the array. This sort of analysis described here is called asymptotic analysis, as it examines how the efficiency of a data structure changes as the data structure's size approaches infinity. The notation commonly used in asymptotic analysis is called big-Oh notation. The big-Oh notation to describe the performance of searching an unsorted array would be denoted as O(n). The large script O is where the terminology big-Oh notation comes from, and the n indicates that the number of steps required to search an array grows linearly as the size of the array grows.
A more methodical way of computing the asymptotic running time of a block of code is to follow these simple steps:
- Determine the steps that constitute the algorithm's running time. As aforementioned, with arrays, typically the steps considered are the read and write accesses to the array. For other data structures, the steps might differ. Typically, you want to concern yourself with steps that involve the data structure itself, and not simple, atomic operations performed by the computer. That is, with the block of code above, I analyzed its running time by only bothering to count how many times the array needs to be accessed, and did not bother worrying about the time for creating and initializing variables or the check to see if the two strings were equal.
- Find the line(s) of code that perform the steps you are interested in counting. Put a 1 next to each of those lines.
- For each line with a 1 next to it, see if it is in a loop. If so, change the 1 to 1 times the maximum number of repetitions the loop may perform. If you have two or more nested loops, continue the multiplication for each loop.
- Find the largest single term you have written down. This is the running time.
Note In case you need a quick mathematics refresher, loga b = y is just another way to write ay = b. So, log2 4 = 2, since 22 = 4. Similarly, log2 8 = 3, since 23 = 8. Clearly, log2 n grows much slower than n alone, because when n = 8, log2 n = 3. In Part 3 we'll examine binary search trees whose search operation provides an O(log2 n) running time.
For example, there are a myriad of algorithms for sorting an array that have differing running times. One of the simplest and most naïve sorting algorithms is bubble sort, which uses a pair of nested for loops to sort the elements of an array. Bubble sort exhibits a running time of O(n2) due to the two for loops. An alternative sorting algorithm is merge sort, which divides the array into halves and recursively sorts each half. The running time for merge sort is O(n log2 n). Asymptotically, merge sort is much more efficient than bubble sort, but for small arrays, bubble sort may be more efficient. Merge sort must not only incur the expense of recursive function calls, but also of recombining the sorted array halves, whereas bubble sort simply loops through the array quadratically, swapping pairs of array values as needed. Overall, merge sort must perform fewer steps, but the steps merge sort has to perform are more expensive than the steps involved in bubble sort. For large arrays, this extra expense per step is negligible, but for smaller arrays, bubble sort may actually be more efficient.
MSDN