Algorithm analysis is an important topic in all aspects of computer science and many other fields, as it can affect your programs complexity and overall performance. The purpose of this series is to slightly cover some of the introductory concepts related to algorithms, and delve into a selection of sorts, searches, and a couple of artificial intelligence algorithms.
What is an Algorithm?
Seven Steps in the Software Life Cycle covered creating a structured, top-down method for the design and implementation of a program. Step four of this process was the algorithm, and was defined as an effective method for solving a problem expressed as a finite sequence of steps. The algorithm must be written very clearly, as not to cause misinterpretation, and is normally done in pseudocode. The algorithm should, when applied to the problem, solve it in a finite amount of time. Basically, you are writing a step by step set of instructions to accomplish a task. This same methodology can be observed in manuals, as they walk you step by step to accomplish different things in a timely manner.
How is efficiency measured?
The Importance of Algorithms mentions that one of the most important aspects of an algorithm is how fast it is. This does not necessarily mean that the algorithm will perform the same for all situations, as performance can be affected by the computers configuration and the implementation of the algorithm’s code. This is why, they explain, you look at the runtime environment versus the size of your input. For example, if the input consists of N integers, an algorithm might have a runtime proportional to N2, represented as O(N2). This means that if you were to run an implementation of the algorithm on your computer with an input of size N, it would take C*N2 seconds, where C is some constant that doesn’t change with the size of the input.
The ordering of the data is important depending on the operation. Let’s take for example a sorting algorithm, which has N amount of integers for it’s input. The best case scenario would be that the data is already sorted, therefore the algorithm would simply run through and realize an already sorted array of data. On the other hand, the worst case would be an algorithm sorted in reverse order. This would cause the algorithm to have to reorder all the data, and would take the longest. Therefore, you will often see analysis refer to worst-case runtime, or the average-case runtime. The table below displays the approximate completion time for algorithms, N = 100. This table will be referred to in future post, as different algorithms are examined.
Disclaimer: Links and Ads might get me paid.
{ 0 comments }
