小埋社区

    • 登录
    • 版块
    • 最新
    • 标签
    • 热门
    • 用户
    • 群组

    C++,二分查找法与斐波那切查找法效率对比

    编程
    1
    1
    176
    正在加载更多帖子
    • 从旧到新
    • 从新到旧
    • 最多赞同
    回复
    • 在新帖中回复
    登录后回复
    此主题已被删除。只有拥有主题管理权限的用户可以查看。
    • Bruce
      Bruce ACG 最后由 编辑

      总有人说斐波那切查找法在极大数据量情况下比二分查找法快,因为斐波那切查找法只有加减法,没有除法,然而二分查找法取中值完全可以右移1位center = (lo + hi)>>1来实现,位移操作是比加减法还要快的操作,因此我决定实践出真实

      PS:有个老哥已经做过实验了,在极大数据量情况下斐波那切查找法确实快一点,但是他的二分查找法是用除法实现的
      原贴:https://blog.csdn.net/fovwin/article/details/9077017
      本贴基于原贴代码,将除法改为位移,将C的callac操作改为C++的new,重新试验

      测试环境:

      CPU: R7 1700 @3.80GHz
      RAM: 32G
      OS: Windows Pro for Workstation 1909
      Compiler: MSVC 2019
      C++ standard: ISO C++17

      输入数据:长度为400,000,000的有序数组,array[i]=i
      对比方式:生成release版程序,从array中寻找数据4613841,用VS自带的性能探测器统计所需时间

      image.png
      二分查找法用时:521ms
      image.png
      534ms

      二分查找法险胜,二者差距几乎可以忽略不计,而数据输入的长度已经远超原贴实验中的长度了,且继续增加长度会引起数组上溢

      结论:两种算法在海量数据查找中性能差距可以忽略不计

      1 条回复 最后回复 回复 引用 0
      • First post
        Last post
      © 2017-2023 小埋社区 All Rights Reserved | 皖ICP备17016228号-2