The term Data Structure refers to how data is
stored and the operations that can be performed on it (Shaffer, 2013). I use "data" as a part of the definition instead of talking
about the storage of information because information is more about pieces of
data working together to answer questions and provide insights. Static data
storage doesn't offer insight in and of itself. Providing insight is what algorithms
are about.
An
algorithm is a method or process taken to solve a problem. Shaffer (2013) lists five traits that make up
an algorithm. The first is that the end result is current, yielding the
desired/intended solution. Second, is that the steps in the algorithm must be
concrete. Concrete means that each step can be understood, executable, and
repeatable, like a cooking recipe. Thirdly, every step must be clear; there can
be no ambiguity. Three steps left would be ambiguous, but 1 meter left is more precise
(assuming "left" in the situation is not itself ambiguous). Fourth,
the number of steps must be finite; you can not arbitrarily add new steps. And
lastly, the algorithm has to terminate, as in it does not get stuck in an
infinite loop. Algorithms often execute their steps by using the operations
provided by data structures to take action on them or based on their values.
While
those features make up an algorithmic design, there's more to good algorithms. Lyseky
(2015) says, "Big O notation is a mathematical way of describing how a
function generally behaves related input size." Two metrics commonly measured
with Big O notation are how long an algorithm takes to run through its process
and how much space the algorithm will use. N is the volume of data fed into an
algorithm, and then, based on the algorithm's steps, the worst-case scenario of
getting to the correct answer is calculated. For something like a linear search,
where each item on a list is checked against a goal, the BIG O for processing
time is just O(N), a 1:1 relationship, and the memory Big O is just (N).
As
computing capabilities have rapidly grown since the inception of modern
computers (look up Moore's law), being resource-conscious is still important. Highly
efficient algorithms enable us to use the increased computing power on new
questions instead of having to use all that computing power to make up for
algorithms with poor performance.
I have applied an algorithmic design by building a tool to calculate the best trade routes in a phone game. The scenario is that six islands buy or sell 12 items to you for various discounts or markups. Your goal is to make the most money; thus I wrote data structures and an algorithm to return the most profitable path. The primary data structure is a graph of island nodes with edges representing the travelable paths. Each island node holds the cost and gain of each item it buys/sells and operations that return how profitable it is to travel each edge. The algorithm starts at a user-provided island and then travels each available edge, calculating the maximum profit along those edges and tracking the current path. Each following iteration branches from every island to every other island, tracking the branched path and its profit.
Single best outward edge from each Island:
The branching at every path gives a Big O(2^N), which is considered very bad (Olawanle, 2022). I only have this branching iterate seven times, and it takes my computer over a minute to process it and; after testing, the algorithm has consistently found two islands worth traveling between repeatedly by this point, making further iterations unnecessary. Besides limiting the number of iterations, I could also improve time performance by only traveling the three more profitable edges instead of all five of them, regardless of profitability. You're welcome to look at it on Git Hub. I originally wrote it in Python and have made a .exe of it for Windows.
Lysecky, R., Vahid, F., Lysecky, S., &
Givargis, T. (2015). Data structures essentials. zyBooks.
Shaffer, C. A. (2013). Data structures and algorithm analysis.
(Edition 3.2). Retrieved from http://people.cs.vt.edu/~shaffer/Book/JAVA3elatest.pdf
Olawanle, J.,
(2022, October 5). Big O Cheat Sheet – Time Complexity Chart
https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/
No comments:
Post a Comment