This week, we wrapped up the end of proving techniques and started talking about efficiency of different algorithms. To conclude the proof part, we learnt some inferences such as conjunction/disjunction elimination, existential instantiation, etc. These rules allow us to do proofs more efficiently by reducing some redundant steps. Then we moved on to calculating the running time for different functions, which refers to the number of steps that function takes.
Running time of an algorithm is an essential part of computer science, because every programmer or software developer has to present an algorithm that's as efficient as possible. Since programmers has to deal with huge amount of data, so we don't want the algorithm produced takes forever to output the result. And to make sure that we -- as starting programmers won't run into that trouble, we will have to first learn how to count the running time of a function. In this week's lectures, we compared bubble sort and merge sort. And we input some specific numbers into the function to determine how many steps each function takes, and then conclude that which one is faster and more efficient. Then we compare the growth factor of each function, i.e. if we double the number of data of input, how will the running time of each function change? Will the ratio of the running time of two functions stay the same? And we found that some functions do better (faster) when there's big amount of data, while some functions run faster if the data is small and run slower and slower as the data gets larger and larger.
No comments:
Post a Comment