Algorithms are an integral part of computer science, and in fact our day to day lives. We use algorithms all the time without thinking about it, in a way our brains are wired to figure out solutions to problems. As computer programmers and application developers we need to know how to translate these solutions into code and ideally effective and efficient code.
In this tutorial series I am going to break a bit from my normal C# Google tutorials. Over the last several months I have seen a lot of people talk about algorithm performance and big O. This is something I learned a very long time ago in collage. After more then 20 years a lot of this has become instinct to me rather then something I was doing with direct intent. When designing an algorithm it is best to know exactly what you are doing and why you are doing it. As someone who has been an application developer for more then twenty years somethings become more instinctive and less purposeful. I have always enjoyed writing tutorials so I thought that I would write a tutorial series on this, in order to get it strait in my own head. I intend to put my normal spin on the series. This will be as simple as possible and the examples will just work.
[wp_ad_camp_3]
Algorithm series
- A gentle introduction to algorithms and bigO
- Algorithms Constant Time O(1)
- Algorithms Linear time O(n)
- Algorithms Logarithmic Time O(log n)
- Algorithms Quadratic time O(n2)
What is constant Time?
Constant time implies that the number of operations the algorithm needs to perform to complete a given task is independent of the input size. In Big O notation we use the following O(1).
In layman’s terms that means that no matter how much data you add the amount of time to preform a task will not change. Back to our book example you could have 100 pages or 10000000 pages the time to find the page wouldn’t matter.
Dictionary / hash table
One of the ways I like to store sets of data is using a dictionary or a hash table. I like to think of the key in the hash table as a primary key in a relational database table. As with primary keys the key in the dictionary must be unique. Lets say you have a list of users each user has an email address. Email address’s must be unique in your system no two users will have the same email address.
I can create a dictionary to store the data.
Dictionary<string,person> data = new Dictionary<string, person>();
data.Add("test@test.com", new person { Name = "Linda Lawton", Email = "test@test.com" });
I load the data into my dictionary making the key equal to the users email address. If my application ever needs to find a specific user I simply look for an item in the dictionary with a key equal to the users email address. I wont need to search though a list of all the users I can go directly to the item i am looking for.
var linda = data["test@test.com"];
It wont matter if I have 10 people or 100000 people in my dictionary it will take the exact same amount of time to find this user.
[wp_ad_camp_5]
Stacks
Here is another good example of constant time. Lets say you work at a dinner. When the dishes are washed each clean plate is placed on the top of the stack of plates. When a new customer arrives you take the first plate off of the stack. Stacks are last on first off it doesn’t matter how many items there are in the stack when you want to remove an item it will always be the last item you placed on top of the stack.
Conclusion
Before you even begin to code a new algorithm you must first consider things about the data it self. Determine out what your best and worse case will be, look at the amount of data you have, and the specs of the machine that will be running the algorithm.
If you can design your code to run in constant time it wont matter how much data you have it will always run at the same speed.
Join me in the next tutorial Algorithms Linear time O(n).