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

栏目: 编程工具 · 发布时间: 6年前

内容简介:阅读本书起源于左耳朵耗子的《左耳听风》 收益颇多,感谢老一辈程序员的无私分享。感谢~大O表示法是一种特殊的表示法,指出了算法的速度有多快。五种常见的大O运行时间

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

第一章 算法简介

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

二分查找法

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

然后剔除无用的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!) 这样的算法包括旅行商算法,这是一种非常慢的算法。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

嵌入式系统软件设计中的常用算法

嵌入式系统软件设计中的常用算法

周航慈 / 2010-1 / 24.00元

《嵌入式系统软件设计中的常用算法》根据嵌入式系统软件设计需要的常用算法知识编写而成。基本内容有:线性方程组求解、代数插值和曲线拟合、数值积分、能谱处理、数字滤波、数理统计、自动控制、数据排序、数据压缩和检错纠错等常用算法。从嵌入式系统的实际应用出发,用通俗易懂的语言代替枯燥难懂的数学推导,使读者能在比较轻松的条件下学到最基本的常用算法,并为继续学习其他算法打下基础。 《嵌入式系统软件设计中的......一起来看看 《嵌入式系统软件设计中的常用算法》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码