2018年10月22日算法图解阅读笔记

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

第一章 算法简介

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

二分查找法

主要思路:假设已知要查找的数据元素的大小,并且输入的要查找的数据集有序。选取中间的数据元素与要查找的元素进行对比。
然后剔除无用的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!) 这样的算法包括旅行商算法,这是一种非常慢的算法。

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

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传