算法第二章上机实践报告

本文主要是介绍算法第二章上机实践报告，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、实践题目：maximum number in a unimodal array

二、问题描述：找出单峰数组（按先增到峰值，再减小的顺序排号）中的最大值，时间复杂度为logN

三、算法描述：本题采用 二分搜索的思想，取最左为l，最右为r。在l<r的情况下，m=（l+r）/2，判断m位置的数是否为峰值：若小于m+1位置，则l=m+1，继续判断；若大于m+1位置，则r=m-1，继续判断。直到m位置的数为峰值，则查找完成。

四、算法时间及空间复杂度的分析：

T(n)=T(n/2）+f(1),n^log21=1,所以T(n)=logn。因为无使用辅助空间，所以空间复杂度为O（1）。

五、心得体会：

这道题因为数组内有一定的顺序，又对时间复杂度要求logN,所以自然的想到了使用二分搜索。这也可以说是二分法合适的一个特点：有序。

想用分治的思想，重点在于几个关键点不能出错：中位数的改变，以及终结条件。但又是这两点比较难想，所以代码跑起来总是有奇奇怪怪的错误，比如一直是输出0，或者输入之后就没反应这类问题。出现这样的问题肯定就是关键点不对，需要重点检查这些部分。

六、分治法的个人体会和思考

比起暴力解法，稍微改变一点代码就可以减少时间复杂度这充分说明了分治思想的优点。

选择使用分治法需要原问题可以查分成几个相同的子问题，且问题规模较大，就可以分治，由子问题的合并得出原问题的答案。但要是子问题有较多重复的时候就需要使用动态规划了。

这篇关于算法第二章上机实践报告的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！