2018-10-22算法图解阅读笔记

zhaoxi_yu · · 952 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

阅读本书起源于左耳朵耗子的《左耳听风》 收益颇多,感谢老一辈程序员的无私分享。感谢~


第一章 算法简介

  • 应用算法与暴力查询之间的效率差 主要以全遍历和二分查找法进行时间效率上的对比,引入算法重要性。

二分查找法

主要思路:假设已知要查找的数据元素的大小,并且输入的要查找的数据集有序。选取中间的数据元素与要查找的元素进行对比。

然后剔除无用的1/2检索集,到最后检索到目标元素返回目标元素,或者找不到返回空值。

实现代码

  • golang版本

func MidSearch(SearchArr [] int, needle, begin, end int, ) int {

for begin <= end {

mid := (begin+end)/2

if SearchArr[mid] == needle{

return mid;

}else if SearchArr[mid] > needle{

end = mid;

}else{

begin = mid+1;

}

}

return -1

}

  • php 版本

function midQuery($begin = 0, $end = 0, $search = array(), $want = null)

{

    while ($begin <= $end) {

        $mid = intval(($end + $begin) / 2);

        if ($search[$mid] == $want) {

            return $mid;

        } else if ($search[$mid] > $want) {

            $end = $mid + 1;

        } else {

            $begin = $mid;

        }

    }

    return false;

}

二分法查找的时间复杂度为O(log^2 n)

大O表示法

大O表示法是一种特殊的表示法,指出了算法的速度有多快。

五种常见的大O运行时间

  • O(log n) 也叫对数时间,这样的算法包括二分查找

  • O(n) 也叫线性时间,这样的算法包括简单查找

  • O(n*log n) 这样的算法包括对数操作的排序算法,因为排序至少需要遍历所有的元素来排序所以,是N,操作的排序时间是对数时间所以是log n

  • O(n^2) N的平方,包括选择排序算法等。

  • O(n!) 这样的算法包括旅行商算法,这是一种非常慢的算法。


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:zhaoxi_yu

查看原文:2018-10-22算法图解阅读笔记

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

952 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传