《算法图解》第一章笔记

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法图解》第一章笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2293字，纯文字阅读大概需要4分钟。

内容图文

最近一门心思都在巩固数据结构和学习算法。

看到网上某大佬推荐的入门算法书——《算法图解》。

看了几章觉得是真的有点洗脑，观点都很简短明了。

记一下每一章的总结，以后没书也能回想起来。

这本书使用python2.7写的算法,看不懂python的不要买！！！
这本书使用python2.7写的算法,看不懂python的不要买！！！
这本书使用python2.7写的算法,看不懂python的不要买！！！

第一章 主要介绍了二分查找和大O表示法。

二分查找原理：有点类似猜谜游戏（假设正确值存在）

- 1-100中，我随便猜一个数，计算机来告诉我猜大了、猜小了、猜对了。

- 二分查找的话，我取1-100的中间数50开始猜，假如计算机告诉我猜大了，那么正确数应该在1-50里面，排除了51-100一半的数字！

- 我从1-50中间数25开始猜，假如计算机告诉我猜小了，那么正确数应该在25-50里面。

- 我从25-50中间数(25+50)/2=37开始猜，计算机告诉我猜对了，得出正确数为37。

二分查找的前提是：有序列表

根据上面的猜谜过程用java手写二分查找
public Object binary_search(int[] list , int item){
	int low = 0; //初始位置
	int high = list.length-1; //终点位置
	int mid ; //中点变量
	while(low<=high){
	    mid = (low + high)/2; //算出中点，中学公式。
		if(list[mid] == item) return mid; //找到了，返回下标
		if(list[mid] > item) high = mid - 1; //猜大了改high
		if(list[mid] < item) low = mid + 1;//猜小了改low
	}
	return null;//没找到
}

一般而言，包含n个元素的有序列表，用二分查找最多需要log?N （以2为底）步，而简单查找最多需要n步。（ps:简单查找就是1-100内猜数字，最多需要猜100次才能找到值）

简单查找和二分查找对比：

由此引出大O表示法。

• 大O表示法指出了算法的运行速度。
• 大O表示法指出了最糟糕情况下算法的运行时间。
• 算法运行时间并不是以秒为单位的，而是从增速的角度进行度量的。

一些常见的大O表示法

• O(logn)，也叫对数时间，这样的算法包括二分查找
• O(n)，也叫线性时间，这样的算法包括简单查找
• O(n*logn)，这样的算法包括快速排序
• O(n^2)，这样的算法包括选择排序
• O(n!)，这样的算法包括旅行商问题解决方案。

其实大O表示法图像化后就像中学学习的函数图。

• f(n) = log n
• f(n) = n
• f(n) = n * log n
• f(n) = n ^ 2
• f(n) = n！
  

旅行商问题：有一位旅行商，要去5个城市旅行。这位旅行商要前往这5个城市，同时确保旅程最短。为此，可考虑前往这些城市的各种可能顺序。


5个城市有 5！= 5 * 4 * 3 * 2 * 1 = 120种组合顺序，需要操作120次算距离。
6个城市就需要 6！= 6 * 5 * 4 * 3 * 2 * 1 = 720种组合顺序，需要操作720次算距离。

规律归纳起来：n个城市有n！种组合，需要操作n！次算距离，所以运行时间为O(n！)。

总结：重点掌握二分查找算法思路，了解大O表示法是怎么回事。去leetcode找标签二分查找的题目练练。

内容总结

以上是互联网集市为您收集整理的《算法图解》第一章笔记全部内容，希望文章能够帮你解决《算法图解》第一章笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---