Ykt*_*ula 5 algorithm complexity-theory
如何分析算法？是什么让quicksort具有O(n^2)最坏情况的性能,而合并排序具有O(n log(n))最坏情况的性能？
这是整个学期的主题.最后,我们讨论的是在算法结束之前必须完成的操作数量的上限,作为输入大小的函数.我们不包括系数(即10N对4N ^ 2),因为对于N足够大,它不再重要.
如何证明算法的重要性是非常困难的.它需要一个正式的证据,并且有许多技术.通常,一个好的特殊方法是计算算法产生的数据传递次数.例如,如果您的算法嵌套了for循环,那么对于每个N项,您必须运行N次.那通常是O(N ^ 2).
对于合并排序,您将数据一次又一次地拆分.这需要log2(n).对于每个拆分,您都会对数据进行传递,这会得到N log(n).
快速排序有点棘手,因为在一般情况下它也是n log(n).你必须想象如果你的分区分割数据会发生什么,每次你只得到分区一侧的一个元素.然后,您需要将数据分割n次而不是log(n)次,这使得N ^ 2.快速排序的优点是它可以在适当的位置完成,并且我们通常接近N log(n)性能.