Importance of algorithms
An algorithm is a set of rules to follow in order to solve a problem.
We use algorithms to improve the performance of our program using the available resources and get the best combination of speed and use of memory.
They are important because programming languages rely on them and because if we find a problem that has already been solved by an algorithm, we can replicate its technique and when appropriate, use it.
We are going to talk about time, but despite speed is an important factor to consider when using algorithms we should still have our priorities as follows:
- Make it work
- Make it right
- Make it fast.
Time
We can and should calculate the cost of our code. When we talk about cost in the context of algorithms , what we mean is time.
A shorthand to know how long a procedure takes is to ask how many lines of code are involved. But there are more factors to consider. If we want to calculate how long does it takes to find if a word contains a specific letter, well, the answer will depend on the size of the word. The cost of performing a function varies with the size of the input, so we describe the cost in terms of the size of the input. We call this cost the time complexity of the function.
Time complexity
Time complexity of an algorithm signifies the total time required by the program to run until its completion and in the worst case scenario. It is defined as a function using Big O notation, an asymptotic notation.
|
1 |
O(n) |
n is the size of the input.
O is the worst case scenario.
* The worst case scenario is one where given an input of a certain size, our function takes as long as possible.
The O function is the growth rate in function of the input size n.
Great resources to learn about algorithms and data structures using Ruby:
- Introduction to algorithms with Ruby
- Grokking algorithms. An illustrated guide for programmers and other curious people. Aditya Y. Bhargava.
- Algorithms and Data Structures in Ruby
- Kanwei/algorithms
- Sagivo/algorithms