Newbie to Newbie: Big O-notation And The Algorithms That Affect It!
Big O-notation And The Algorithms That Affect It!
Search algorithms in a programmer's code can have no effect, some effect, or a significant effect on big O-notation time and space complexity. Big O is used to find the time it takes to fully execute an algorithm in mathematical form. A more straightforward view of big O is remembering Algebra, the exponent value of x, and the order they should be (i.e. n² - 2n + 1). Only the highest exponent is kept with a big O-notation, and the constants (numbers) are dropped. In the example above, the time complexity is O(n²). To understand space complexity, one would simplify the given example to (n - 1)(n - 1). The programmer's code using algorithms to find (n - 1) should achieve the fastest runtime closest to O(n) and reduce the space needed to store to memory.
How do You Know Which Algorithm to Use?
The data structure you use for your programming code is determined by what you need your program to accomplish. Your program may need to build lists, arrays, linked lists, stacks, queues, trees, etc. Your program may also use a combined combination of data structures that algorithms in the code will help the program achieve the fastest runtime closest to O(n) and limit the space needed for memory storage.
The picture above is written in Java's programming language and utilizes a list that cannot change, an array list that can be updated, and a linked list that will hold the combined indexes of the list and array list. One way an algorithm can be written to solve time and space complexity for O(n) execution is by requesting input from the user to help guide the operating system's memory allocation and never use additional storage. Your lists, array lists, and linked lists can be written to be accessed quickly with searching. Knowing which type of searching algorithm to use can speed up or slow down O(n).
Algorithms And Design Comparisons
A program's code works in a linear motion where there is a start and an end. Your algorithm can be written to reference parts of the program that were previously created. These references are called pointers in Java syntax; if they are not written correctly, they can affect O(n) runtime.
In the picture below, you will see a for loop that runs linearly to search the weekAgenda linked list to return the nested index of the combined city array and dayOfWeek list values. What you do not see is the code that allowed the user to create the weekAgenda linked list.
The for loop is faster to use linearly because the purpose was to provide the user with options to choose from, and it was a short list. If the purpose was to have the user enter a weekday and choose a date in a month, a binary search would be utilized because it is faster to divide the dates and locate them based on a sorted list in alphabetical/numerical order. A purpose helps guide which algorithm to implement and the program's design.
This program pictured above uses algorithmic recursion to call or reference the weekAgenda linked list, with pointers to the city name chosen to update for a chosen weekday. The program's algorithm was written so the user could communicate with the system and remove the programmer from further dictating what the system should do. When the user chose the weekAgenda index to update, the program already knew where to point to for the weekday and city. The only thing left was to allow the user to choose a new city name, and the algorithm was coded to tell the system to remove the previous link and replace it with the new link in the same format initially created. When an index is known, the system can retrieve the information faster than by writing more search algorithms.
Real-World Applications
Avid gamers like myself see these algorithms and designs in ranking lists. The list may show the top 10 and give options to view the top 50 or 100. You may even see your ranking number associated with your username on this page. This helps users challenge themselves to be seen on top and boost their scores. For some, it may feed into more anger management classes. Many algorithms are being executed in this scenario, such as adding up the total points per player, queues for those pesky commentaries that don't show the skip button (tapping is relentless), stacks for level transitions, arrays for choosing weapons, and so much more! In gaming, a poor choice of data structure relates to the player's quality of service. The purpose is definitely an essential factor in writing the algorithms.
The example in the pictures was a program I created to help users create a weekly agenda of travel locations in my CPT 307 Data Structures & Algorithms course. It was written with 222 lines of code and could have been simplified using classes between if-else if-else statements and while true loops. Classes help limit parts of the program from taking up more memory than needed and help with faster execution of the algorithms using Java syntax. If I wrote the code in Python syntax, I still would use 222 lines or possibly more. Of course, experienced Java programmers could write my code more concisely. The goal here is to remember the lines help you build your purpose first. If you want to work on simplifying it for O(n), you can. This program can also utilize a queue or stack to remove unnecessary classes from running.
Comments
Post a Comment