Throughout the whole semester, especially the last half, we were dealing with a lot of recursion practice.
Recursion is a great way of solving recursive problem such as Tower of Hanoi. Even for some of the problems which may seem unnecessary to use recursion, the implementation of it is quiet heuristic. For example, we can construct recursive linked list by claiming its nxt to be linked list too. The basic operation of it such as deletion and insertion became recursive too.
The most powerful implementation of recursion in our study I guess is tree. Including general tree, binary search tree or even some class with similar structure with tree. For instance, the minimax strategy we used in our assignment 2.
At the end of our lectures, we get to learn about more about sorting, which led us to know about efficiency of our programming. Their are many method of sorting, the most basic one of bubble sort, which takes order of O(n^2) to sort a list of data. Instead of sorting things brutally, we have trade-off between space and time and sometimes between time and time. For example, binary search tree allow us to search things quickly, but if the tree is unbalanced, given the worst situation where the tree is reduced to linear structure. So what we need to do is to make it balanced first.
There are many sorting like quick sort, selection sort, and merge sort etc. Efficient sorting is important to optimizing the use of other algorithm such as search and merging algorithm.
No comments:
Post a Comment