Data Structure and Algorithm Design and Efficiency
When learning to program,
it is essential to understand how to apply algorithmic design and data
structure techniques to develop a structured program. An algorithm is a set of
instructions that mandates how data will be manipulated to solve a problem or
task (UT, n.d.). In contrast, a data structure implements the storage,
organization, and retrieval of data (Ianurag, 2023). Figure 1 depicts the
difference between algorithms and data structures (Ianurag, 2023). Data
structures and algorithms are typically used together as storing data to be
implemented in an algorithm may be necessary.
Figure 1
Difference between Data
Structures and Algorithms
When designing a program, the data structure or algorithm
choice usually depends on the task's requirements. While several solutions may
work, some may be more efficient than others. When choosing a data structure,
it is crucial to understand the relationship that the framework of the data
structure will provide. Some examples may be that data in a queue will have a
first-in-first-out structure, data in a stack will have a first-in-last-out
structure, and data in a hash table will be retrieved by a key-value pair
(Shaffer, 2013). The rigid framework of most data structures helps make the selection
choice more decisive.
The
complexity of the algorithm defines algorithm efficiency. Time and space
complexity is a standard used to measure this efficiency. Time complexity is the number of steps to complete the algorithm. In comparison,
space complexity determines the amount of storage required to process the
algorithm with respect to the input size (University of Cape Town, 2014). When
considering the time and space complexity of an algorithm, it is typically to
evaluate the asymptotic complexity of the algorithm. Asymptotic complexity is
the algorithm's behavior as n (number of inputs) goes to a specific value (such
as infinity) (Shaffer, 2013). The big O notation may measure asymptotic
complexity. The big O notation evaluates the worst-case scenario of an
algorithm based on the highest order with respect to the input. The Complexity
Analysis gives an excellent example of selection sort defined by time and
space complexity as evaluated by big O notation.
To
better understand algorithm efficiency, consider the choice of recursion versus
iteration. Several problems or tasks may be solved using either technique, so
why choose one over the other? Figures 2 and 3 depict the differences between
recursion and iteration (Dkp1903, 2023). When considering the asymptotic complexity
of recursion and iteration, iteration offers a lower time and space complexity
for a large value of n. Follow the links to understand further how the big O
notation is used to evaluate recursion
and iteration
(My Code School, 2012) (Techdose, 2020).
Figure 2
Recursion versus
Iteration
Figure 3
Recursion versus
Iteration Continued
While it may appear that iteration should always be the
optimal choice, why do we use recursion? Two design goals of an algorithm are
said to be: 1.) easy to understand, code, and debug. 2.) to efficiently use a
computer’s resources (Shaffer, 2013). Recursion is done with less code and is considered
easier to debug and read than iteration. Some problems are also naturally
recursive, making recursion the ideal method of execution (Kartikgoel, 2023).
When implementing an algorithm (especially with a small n value), recursion may
be a more desirable choice than iteration. This example highlights that it is the
programmer's choice of designing and implementing an algorithm but creating the
most efficient algorithmic design requires intimate knowledge of data
structures and algorithms. Furthermore, a programmer needs to assess the specific
requirements of the task and the dataset. While it is said that the two goals
of algorithm design may sometimes be contradictory, it is the programmer's job
to weigh the advantages and disadvantages of the choice implementation
(Shaffer, 2013).
References
Dkp1903. (2023, May 22).
Difference between Recursion and Iteration. [Infographic] Geeks for
Geeks.
Difference
between Recursion and Iteration - GeeksforGeeks
Ianurag. (2023, April 3).
Difference between Data Structures and Algorithms. [Infographic].
Geeks
for Geeks. Difference
between Data Structures and Algorithms - GeeksforGeeks
Kartikgoel. (2023, May
20). Recursion in Java. Geeks for Geeks.
Recursion
in Java - GeeksforGeeks
My Code School. (2012, October
10). Time and Space Complexity Analysis of Recursive
Programs
– Using Factorial. YouTube.
https://youtube.com/watch?v=ncpTxqK35PI&si=hyzaTpaUFOTBjkCZ
Shaffer, C. A. (2013). Data Structures and Algorithm
Analysis (Edition 3.2). Retrieved from
http://people.cs.vt.edu/~shaffer/Book/JAVA3elatest.pdf
Techdose. (2020, February
3). Finding Time Complexity of Iterative Programs | Part – 1.
YouTube.
https://youtube.com/watch?v=aDxhlwqF1k4&si=BHe5hdKOv6KUMcd2
University of Cape Town.
(2014). Sorting,
Searching, and Algorithm Analysis. Retrieved from
http://python-textbok.readthedocs.io/en/latest/Sorting_and_Searching_Algorithms.html
University of Texas. (n.d.). Complexity Analysis. University of Texas.Data Structures: Lecture 2 (utexas.edu)
Comments
Post a Comment