数据结构与算法（二）：寻找峰值

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法（二）：寻找峰值，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含871字，纯文字阅读大概需要2分钟。

内容图文

一维：

峰值规定：a[i]>a[i-1] and a[i]>a[i+1]，假定只存在一个峰值

1

2

1

9

5

0

 

 

例如9就是一个峰值

方法一：顺序遍历，时间复杂度O(n)

方法二：分治策略，将列表折半查找，第一次查找n/2，左右两边哪一边大继续折半查找哪一边

def search_peak(alist):
    l=0
    r=len(alist)-1
    while l<=r:
        mid=(l+r)//2
        if mid==0 or mid==len(alist)-1:
            return mid
        else:
            if alist[mid]<alist[mid-1]:
                r=mid-1
            elif alist[mid]<alist[mid+1]:
                l=mid+1
            else:
                return mid
    return -1
    
print(search_peak([1,1,1,1,1,2,3,5,7,9]))

这种写法并未考虑相邻两数相等情况的处理，并且只能处理查找一个峰值的情况，如果查找多个峰值，即使利用二分查找复杂度仍然会降为O(n)

时间复杂度分析：

1，首先进行一次折半得：T(n) = T(n/2) + O(1) 

2，n为剩余元素，O(1)代表进行一次比较

3，再次进行折半得：T(n) =  T(n/4) + O(1) *2

4，以此类推得：T(n) = T(n/2^k)+O(1)*k  #注意前面是幂，后面乘

5，令n/2^k=1（表示最后剩下一个元素）得：k=log2n

所以T(n) = O(1)*log2n = O(logn)

 

 

内容总结

以上是互联网集市为您收集整理的数据结构与算法（二）：寻找峰值全部内容，希望文章能够帮你解决数据结构与算法（二）：寻找峰值所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---