分治算法实验-单峰序列问题

古城微笑少年丶 2022-07-16 00:18 132阅读 0赞

# 问题描述 #

给定含有n个不同元素的数组L，如果L中存在xi使得 ，则成L是单峰序列，称 是L的峰顶。完成下面的任务：  
（1）设计一个分治算法找到L的峰顶，编程调试正确。  
（2）从理论上分析算法的时间复杂度。  
（3）写出实验报告

# 问题分析 #

1、给定的L为单峰序列，最直观的寻找方法，直接遍历，第一个x\_i>x\_(i+1) ，x\_i即为单峰序列的单峰。  
2、若要采用分治法，即将n个元素的数组分为差不多大的两个n/2的数组。根据分界线，直接淘汰掉一半，缩小范围。  
3、分界的类型：  
![x\_(i-1)> x\_i> x\_(i+1)][x_i-1_ x_i_ x_i_1] 降序，说明峰顶在i及i左边。  
![x\_(i-1)< x\_i< x\_(i+1)][x_i-1_ x_i_ x_i_1 1] 升序，说明峰顶在i及i右边。  
![x\_(i-1)< x\_i> x\_(i+1)][x_i-1_ x_i_ x_i_1 2] 即发现峰顶。  
其他情况，不符合单峰数列的定义，结束  
4、算法设计，此处采用c++程序语言描述算法：

int findTop(int* theArray, int left, int right)
    {
        if (left == right) return left;     // 如果找到了，返回下标
        int index = (left + right) / 2;     // 没找到继续找
        if (theArray[index] < theArray[index + 1] && theArray[index - 1] < theArray[index])         // 上坡，查右半部份
            return findTop(theArray, index , right);
        else if(theArray[index] > theArray[index + 1] && theArray[index - 1] > theArray[index])     // 下坡查左半部分
            return findTop(theArray, left, index);
        else if(theArray[index] > theArray[index-1] && theArray[index] > theArray[index+1])     // index就是峰顶，可以返回index
            return index;
        else
            return -1;
    }

5、时间复杂度分析  
设n元素的数组时间复杂度是T\_n ,则T\_n=1+ T\_(n/2)。由该关系式解得，时间复杂度应为：O(〖log〗\_2 n)

[x_i-1_ x_i_ x_i_1]: /images/20220716/1b58e6ca5ff940109553da79a1b783ce.png
[x_i-1_ x_i_ x_i_1 1]: /images/20220716/ef7e719852bb407289d023934bafbc10.png
[x_i-1_ x_i_ x_i_1 2]: /images/20220716/2ff468edea5c4a52b0f4860fcbe2e97d.png