算法第二章上机实验报告

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

1，实验报告名称

7-1 maximum number in a unimodal array 

2,问题描述

You are a given a unimodal array of n distinct elements, meaning that its entries are in increasing order up until its maximum element, after which its elements are in decreasing order. Give an algorithm to compute the maximum element that runs in O(log n) time.

3,算法描述

利用分而治中的递归算法找到其最大值，同时需要注意最大值处于最左端或者最右端有可能导致数组越界的情况

4，时间复杂度与空间复杂度

时间复杂度：采用了二分算法。

分解子问题：时间复杂度为O（1）

子问题：时间复杂度为O（n/2）

总时间复杂度为O（logn）

空间复杂度：空间复杂度为O（logn）

5,心得体会

单峰数组求最大值需要考虑峰在最左端或最右端，于是在循环中需要判断mid值是否已经到达了两端位置，若已经到达，则最大值即为左或右两端。

6，分治法的个人思考

分治法的思想把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并

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