Introduction
If you've been writing code for a while or just starting your developer journey chances are you've had the word Data Structures and Algorithms
thrown around, read about it in a publication or heard it from that YouTube developer roadmap video you probably watched a while back. but what is this, what does it necessarily mean and why should you learn it? That's what we'll be taking a look at today.
Algorithm
So what is an algorithm? An algorithm can best be described as a set of well-defined instructions required/taken to solve a particular problem. It takes an input and produces the desired output. Think about it like a series of steps taken to accomplish something.
e.g) Assume we are in a school system and need to get to class
in the morning every day. Our get-to-class algorithm might
look something like this:
- Wake up, then take a shower
- Have Breakfast
- Make the Bus
- Get to our Locker and pick up our books for the morning session,
- then head to class
This is a good example and will be our mock Algorithm for the rest of this mini-tutorial.
Data Structure
what is a data structure? A data structure is a way of storing data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently. e.g Arrays
In the example above our data structure would be our Locker where we pick and store our books.
Types of Data Structures.
Data structures can be divided into:
- Linear Data Structures - In linear data Structures the elements are arranged in sequence one after the other. Since elements are arranged in a particular order they are easy to implement. e.g. Stack or Queue However as the application scales/ or becomes larger linear data structures might not be the best choice as operational complexities can become quite taxing.
e.g) Using our example above lets assume there are 1000 lockers and we
forget where our locker is, we would have to go step by step trying every
locker assuming we have to operate in sequence. This is a perfect
example of how a linear data structure might not be the best solution
as your application scales.
- Non-linear Data Structures - Elements in a non-linear data structure are not arranged in any sequence, Instead, they are arranged in a hierarchical manner where an element will be connected to one or more elements. Non-linear data structures are further divided into **graph **and tree-based data structures.
e.g Using our example above rather than our lockers being operated in sequence
we can assume they are grouped respectively to our classes. That would make
finding our locker way much easier than approaching the problem in a linear
step-by-step approach as our worst-case scenario would be accessing the
number of lockers for students in our class rather than the entire school.
This is why learning data structures is important, it helps you structure your
project in the best way possible before you even begin writing your code.
Now that we've looked into an overall view of data structures, let's look into the study of these algorithms.
Asymptotic Analysis
Algorithms may not have the same performance for different types of inputs. When the input size (the data being manipulated) changes the performance of the algorithm might change. Asymptotic analysis can be defined as the study of this effect i.e. the study of change in the performance of an algorithm with a change in the order of the input size.
Asymptotic Notations
These are the mathematical notations that help predict this effect. They describe the running time of an algorithm when the input size tends towards a particular value or a limiting value. There are 3 major asymptotic notations:
Big-O Notation
Omega Notation
Theta Notation
Big-O Notation
This checks for the worst-case scenario of an algorithm. It can best be described as the study of how well an algorithm scales with respect to a change in its input size(n) considered in the worst-case scenario. It represents the upper bound of an algorithm.
In our example above our worst-case scenario would be the assumption that we find our locker as the last locker remaining after checking all the rest.
Omega Notation
Omega Notation represents the lower bound of an algorithm i.e the best-case scenario.
In our example above our best-case scenario would be the assumption that we find our locker as the first locker we try.
Theta Notation
Theta notation represents the lower and upper bound of the running time of an algorithm. It is used to predict/analyze the average running time of an algorithm.
In our example above our average-case scenario would be the assumption that we find our locker halfway through our search.
Conclusion
This concludes our beginner's guide to data structures and Algorithms. Hope that gave you a general idea of what data structures and algorithms are, why it is important to understand them and what to look into as you begin your studies.