So far,
this course has been fun and interesting. Earlier we were learning about
various aspects of python as well has strategies to code. However, now we began
learning about the efficiency of code. We were told that programming is one
thing, however, programming efficiently is another thing. Writing code that is
inefficient will be useless as it will take too long to run (running time
determines efficiency), therefore a programmer needs to make sure his code runs
accurately as well as efficiently. This can be done by avoiding repetition (one
major problem that makes a program inefficient).
The
examples we took up in class, to show how efficiency can vary, were the
examples of various sorting algorithms. The reason behind this was that all
algorithms performed the same task, however, in a varied manner. The algorithm that sorted in the least
possible steps was the most efficient and the quickest. We also looked at how
the problems given impact the efficiency of various codes. This was done during
the lab where we ran 3 types of problems. In the first case, we gave the
algorithms a sorted list. In the second case, we gave the algorithms a randomly
unsorted list . In the third case, we gave the algorithms a list that was
unsorted and in the order of largest to smallest. Various algorithms performed
differently due to the difference in code. We then mapped the run time and
found that the bubble sort algorithm took the longest for all 3 cases and the
insertion and selection sort’s times varied depending on the situation. We then
also saw how tweaking the algorithms could improve the run time, for example
preventing the repetition of the function-len(). Other than these sorting
algorithms, in class we also learned about the tim sort and quick sort.
We also
learned about Big O notation. We learned that Big O is used to classify
algorithms by the manner in which they respond to a change in input size n. The
best response of an algorithm could possibly have is O(1)-(where the algorithm
completes the task in one step), and the worst was O(n!)-(where the algorithm
does the task in n factorial steps). We then classified various algorithms
using big O notation including the various sorting algorithms. We were told
that programmers always look at the worst case when classifying an algorithm
(however, average case and best case are also looked at). Regarding the sorting
algorithms, we learned how Selection
sort works by repeatedly selecting the smallest remaining item and putting it
where it belongs therefore having a time complexity/Big O of n^2 under both the best and worst case. This
is clearly because it has to go through n items n times. We also learned that Insertion
sort works by repeatedly inserting the next item where it belongs in the sorted
items at the front of the list therefore having a best case of O(n) when the
list is sorted and O(n^2) when the list is unsorted(especially from largest to
biggest). As we know that bubble sort compares each item to the item next to it
no matter what, therefore it has best case scenario of O(n) if the list is
sorted and worst case O(n^2) if the list is completely unsorted.
Overall,
I found this section of the course very helpful and interesting. It taught me
that a programmer doesn’t only aim to make his/her code work, he/she aims to
make the code work and that to efficiently and quickly.
