Well, hello, Internet and welcome to my Data Structures and Algorithms tutorial.
What we're going to do here is probably explore the most important concepts that you will learn as a
computer programmer.
What I'm specifically going to do in this video is explain why data structures and algorithms are important
and then provides a introduction to Big O through some coding examples.
So I have a lot to do.
So let's get into it.
All right.
Whether you know this or not, computer science is the science of solving problems.
And more specifically, the solution to that problem is what we call an algorithm.
And basically an algorithm is just a step by step list of instructions that lead to a solution.
And just to provide you an example, let's say you can drive a car just simply by understanding how
the brake, the gas pedal, the steering wheel and the turn signal work.
And that is everything you need to know to get in your car and move from one place to another.
The manufacturer, however, of that car needs to understand how every single part of the car works,
and it is their job to provide you with that easy to understand interface.
As a programmer, you must understand those details and also must provide an easy to understand interface
for your users.
So why should we study data structures and algorithms?
Well, first off, we are very often going to need to define custom types of data.
And like I said before, we need to also provide an easy way for users to be able to access and use
that data.
Now, by studying the most useful data structures, we are going to be able to better design custom
versions that we need.
And also in regards to working with algorithms and understanding ironclad algorithms that have been
created to effect only be able to solve problems, we will begin to recognize how to utilize those solutions
to solve numerous other problems.
So you may wonder, well, how do we know one algorithm is better than another?
Well, first off, we have readability.
We also need to be concerned with how much memory a algorithm would consume.
Execution time, of course, and also extremely important how well that algorithm can scale.
Now, I'd like to explore some of these concepts by actually working through the optimization of an
algorithm.
So to test how well my algorithm is performing, I'm going to import time it, which is going to allow
me to do that and I'm going to create functions to find the optimum best way to some values.
So let's go and use a for loop, which is something that is very commonly done.
However, you're going to see that it's not very optimized.
So we're just going to go in and cycle through a list of values.
And as we cycle through these values, I'm going to go and just add them to our final solution here.
And then after we are all done with that, I am going to return whatever our solution is.
Now, let's say that we would like to also come in here and try different ways so there's multiple different
ways to loop.
So why don't we use a while loop and let's see which one is the most efficient.
So I'm also going to create get some to again, we'll have our solution.
But of course we're also going to need to increase the value of I as we cycle through this and for this
because we're using a while loop, I'm going to say while I is less than our maximum value, I want
to continue or it's a maximum number that is, I want to continue to cycle.
And if you're used to going and working with algorithms, you're going to notice that since we're creating
all these other different variables, that that is going to slow down our execution time.
But let's come in here and let's test this to see that indeed that is true.
So again, we're going to be using and the only reason these are underlined is because there's not an
extra space there.
All right.
So we have our two functions and we want to see which is more efficient, our for loop solution or our
while loop solution.
So we're going to use time at to do that.
So basically what we need to do well, let's come in and we'll say something like testing, get some
and also testing, get some to and then time it way it's going to work.
Let's go and print out all of our different tests.
We'll say time it and we'll specifically use repeat.
The way this works is you pass in the actual function.
You want to run.
So this is going to be in our first situation, get some and let's say that we want to add up.
Um, how about 100,000 values?
Well, after we do that, we're going to define how many times we want to repeat our timer and I'm going
to say five, and then the number of times to execute the function I'm going to in this situation,
say one, and then we need access to these outside functions.
And how you define that, as you say, globals is equal to globals and make sure you spell globals right.
All right.
So this is going to give us our results for our calculations, and then we'll be able to figure out
which is the most efficient way of cycling and adding values either for loops or while loops.
So change this to get some to and then let's test it and see which works.
And if we run it, you're going to see that, yes, indeed.
Our hypothesis was correct.
It takes longer to use our while loop than it does to use our for loop.
And once again, the reason you can see there's similar results as we cycle through here and look at
the different tests.
And the main reason why is we're creating more variables whenever we're using a while loop versus the
for loop that is more simplified.
However, after doing a little bit of research, you find out that there is in fact a algorithm that
exists that is going to cut down on the need to repeat steps over and over again.
As you can see here, we're cycling through, we're getting a value, we're adding that value to solution.
And we're doing that over and over again.
And that is true with the while loop as well as the for loop.
So you decide to test out this algorithm you found online and you want to see if it is indeed the most
efficient.
And that algorithm, we're going to call it our new improved get some three and it is also going to
get a maximum number.
And we could abbreviate this.
Let's say we want this to be m n instead, and we can do that everywhere here just to make it a little
bit smaller and more condensed.
And let's do that for all of these so that we get the, you know, so we don't falsely believe that
changing the variable name is going to affect our results.
And with this algorithm, we just go maximum number times maximum number plus one divided by two, and
we are going to test it and see if indeed this is going to save us some time.
So let's go and copy this, paste that in there and get some three and get some three.
Everything else is exactly the same and let's test it.
And indeed, whenever we run it, you can see that not only is that more efficient, it is dramatically
more efficient.
And like I said before, it is the most efficient algorithm because mainly it doesn't contain repeated
steps.
And what's even better is this is going to allow it to perform well as the number of values dramatically
increases.
So let's instead add a couple zeros, let's add two zeros to these and see how dramatically better this
algorithm is.
And as we run it, you can see the get some original is getting really slow.
The get some two is going to be even slower yet.
And yet the performance of our new improved algorithm is dramatically better and we'll continue to be
better as the sums increase.
However, even though we can go and use these timing functions, simply calculating time is not always
the best way to judge an algorithm's overall performance because it's largely based off of the computer
being used as well as the language being used with the algorithm.
And in videos that follow this one right here, we're going to find that it is actually better to quantify
performance based on the number of steps the algorithm requires.
And this is whenever we get into what is known as big O notation here, the O is going to refer to the
order of magnitude, which is a measure of how well an algorithm is going to scale as the amount of
data being consumed increases.
And what I mean by that is how well it performs as it increases from, say, a ten element list versus
a 100 element list.
And to give you an example of this, let's say we have an algorithm that's 45 and the power of three
plus 20 and to the power of two plus 19.
Well, if N.
Is equal to one.
In this situation, we would get a value of 84.
Now, what I'm trying to do here is to define the part of the algorithm that has the biggest effect
during the calculation of the answer.
So let's instead say that we would go and take the value of N up to two.
Well, in that situation, our answer would go from 84 to 459.
And it doesn't take very long as we increase the value of N that we start to realize that plus 19 within
our algorithm really isn't going to matter that much.
And also we are going to notice let's comment this.
So it's a little bit easier to see if we would take N to a value of ten.
Well, in that situation, the answer is going to be 47,019.
So in that situation, you're also going to see that not only does the plus 19 part of our algorithm
not matter that much in regards to performance, but also n to the power of two is also really not going
to matter so much because of course, if the value of N is equal to ten and to the power of two is only
going to be equal to 100.
So big difference between 100 and 47,000.
And also if we would go and calculate 45 n to the power of three, we see that that comes out to 45,000.
So we know from analyzing this algorithm that n to the power of three is going to have the greatest
effect on our final answer.
So in that situation, if we would use big O notation, we would realize that because n to the power
of three has the greatest effect on our final answer, we would say in that situation that this algorithm
has an order of n to the power of three or using big O notation o and to the power of three.
And as I'm going to cover in the videos that follow this, there is multiple different ways to define
the performance of algorithms.
Using big o notation, you're going to see a one by one relationship, which basically means that no
matter what happens, the algorithm is always going to perform exactly the same.
And then as well, I will cover all the other different big O notations that you are likely to come
across on your programming journey.
So follow along in the videos that come up, and I will give you examples of how each of these work.
Of course, inside of the resources folder, we have everything that I have covered here and like always,
please leave your questions and comments down below otherwise till next time.