算法图解阅读笔记开始

2019-02-19

算法图解

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

上一篇：算法图解阅读笔记-递归与快速排序算法