Finally I have finished writing all of my
midterms and submitted all my projects. I thought it was time to tackle a
problem in my slog!
At the beginning of this week Danny introduced a function which purpose was to find the slice that had the maximum sum of a sequence of integers. The function
that he showed us was a solution using O(n3) time complexity. As a challenge he proposed we
find a solution using O(n2) time complexity, and even trying O(n) time complexity. Here is my attempt to solve that problem!
1
UNDERSTANDING THE PROBLEM
o The problem given by Danny was
to take the original function using O(n3) time complexity and improve its efficiency by
using O(n2) time efficiency. After this to further the
efficiency of the function, I must try to simplify the function further and use O(n) time efficiency.
o
The
unknown of this problem is O(n2) and O(n) time complexity. The information given in this
problem is the original function, which allows us to create a solid example to
base the testing of all of our simplified functions.
Ex:
With this type of function you begin with a sequence of integers, and the goal
is to find the slice with the largest sum. Here is the example I referred to
when solving this problem:
L = 5, -7, 3, 5, -2, 4, -1
*The
slice highlighted in yellow represents the slice with the largest sum, that sum
being 10. I will use this same sequence as a test for all my functions
o
With
the first function, and with the help of an example simplifying this function
is very possible. In order, to do this I must first dissect the function and
understand exactly the purpose of each loop.
2
DEVISING A PLAN
o
Looking
at the original function I know that looking at all the possible slices
requires O(n2) time complexity, and then for each of those
slices when use O(n) time complexity.
o
The first challenge here is to re-create this
function using O(n2) time complexity
o
To
do this I took the original function, and with my test sequence of integers, I
kept in mind that my expected output would be 10.
o
Then
I began to write out a plan where instead of doing 3 iterating loops I reduced
it to just 2 loops
o
I
did this process again for O(n) time complexity, yet this time it was slightly
easier for me, and took less time to plan out my approach.
o
My
approach for O(n) was simply to take the sequence of integers
and calculate the largest sum that ends in a certain position. You would do this
until you have looked at all the slices that are possible, and this will
determine which slice has the largest sum.
3
CARRYING OUT THE PLAN
o
Now
it’s time to carry out my plan, and take all of my thoughts, and put them into
code. Here are the two improved functions that I wrote:
O(n2) time complexity solution:
Although this function definitly is an improvement from the O(n3) time complexity, there is still
room for improvement.
O(n) time complexity solution:
This time complexity (O(n)) represents the fastest algorithym for a
max slice problem.
4
LOOKING BACK
o
Looking
back at my code I believe I went about this in an efficient way, and everything
seems to work fine. There definitely is other ways of going about this problem,
such as using for loops instead of my while loops. This would reduce the amount
of variables, but I decided to keep it consistent with the original example
used by Danny.
.png)
%2Bcommented.png)
.png)
.png)