This week we mainly focused on
algorithm runtime analysis, which is an estimated amount of “steps”
(lines of code) which an algorithm takes to complete a task. This
analysis is not specific to any programming language, and an
algorithm can be mathematically proven to be O(x) (where O means big
O and x is some function or a constant). This provides an upper-bound
(ie. worst-case runtime) on an algorithm or function. For example,
the binary search tree example we went over in class had an
approximate runtime of O(log n) (instead of n, so it was faster). The
reason that we have been focusing on linked and recursive structures
(such as binary search trees) is that they often can reduce runtime
and are more efficient.
We also went over the selection and
insertion sorts and analyzed their upper-bounds. These sorts are not
very efficient, and I have a feeling that recursion will be a key
element in other, more efficient sorting algorithms. I already took
CSC165 as well as CSC108, so most of what we did in class this week
was review for me. I started the second part of the second
assignment, as well as finished the third exercise this week.
Some sort of runtime analysis for a
merge sort algorithm.
(http://i.stack.imgur.com/j1mZV.png)
No comments:
Post a Comment