2018-10-22算法图解阅读笔记
2018-10-22 本文已影响0人
zhaoxi_yu
阅读本书起源于左耳朵耗子的《左耳听风》 收益颇多，感谢老一辈程序员的无私分享。感谢~
第一章 算法简介
- 应用算法与暴力查询之间的效率差 主要以全遍历和二分查找法进行时间效率上的对比，引入算法重要性。
二分查找法
主要思路：假设已知要查找的数据元素的大小，并且输入的要查找的数据集有序。选取中间的数据元素与要查找的元素进行对比。
然后剔除无用的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!) 这样的算法包括旅行商算法，这是一种非常慢的算法。
