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!) 这样的算法包括旅行商算法，这是一种非常慢的算法。