算法快学笔记(一):算法入门

栏目: 编程工具 · 发布时间: 5年前

内容简介:“算法”一词在不同的书籍以及网站上可能会存在一些差异,但是下面的定义个人觉得最为贴切:在很多场景下,数据规模越大,越能体现优秀算法的价值,接下来将以猜数游戏为例进行说明优秀算法的重要性。假设 A随便想了一个1到100中的某个数字让B猜,B可以有两种方案:

1. 算法的定义

“算法”一词在不同的书籍以及网站上可能会存在一些差异,但是下面的定义个人觉得最为贴切:

1. 算法代表着用系统的方法描述解决问题的策略机制
2. 能够对一定规范的输入,在有限时间内获得所要求的输出
3. 一个算法的优劣可以用空间复杂度与时间复杂度来衡量

2. 论优秀算法的重要性

在很多场景下,数据规模越大,越能体现优秀算法的价值,接下来将以猜数游戏为例进行说明优秀算法的重要性。

假设 A随便想了一个1到100中的某个数字让B猜,B可以有两种方案:

  1. 简单查找:从1开始猜,一直猜到A想的数字为止。
  2. 二分查找:一半一半的猜,先猜50,如果小了,这时候就排除了1-50的数字!。接下来,你猜75,如果大了,就排除了75-100。以此类推。

接下来对两种方式进行说明与比较

2.1 简单查找

该方法的优点是简单,只需要从1一个个的猜,就一定能猜到。但是如果猜测数字的范围非常的大,且猜的数字非常靠后,将会使用较多的时间。

2.2 二分查找

二分查找是一种算法,其输入是必须是一个有序的元素列表。每次猜都从列的中间元素开始,如果大了,就过滤掉比猜测值小的那一半数字,反之亦然。

实现代码如下:

// 使用二分查找法,在有序列表intList中查找target,返回对应的索引
func BinarySearch(intList []int, target int) int {
	start := 0
	end := len(intList) - 1
	for {
		if end <= start {
			break
		}
		mid := int((start + end) / 2)
		if intList[mid] == target {
			return mid
		}
		// 如果mid处的值大于目标值,就在mid之前的数据中搜索
		if intList[mid] > target {
			end = mid-1
		}
		// 如果mid处的值大于目标值,就在mid之后的数据中搜索
		if intList[mid] < target {
			start = mid+1
		}
	}
	return -1
}

2.3 简单查找VS二分查找

如果列表包含100个数字,简单查找的方式可能要找100次才能找到结果,而二分查找法由于每次查找都会过滤掉一半的数据,因此最多只需要7次(log100)就能找到结果。这个级别的数据,结果看起来差距还不是很大。

如果列表包含40亿个数字,简单查找的方式可能要找40亿次才能找到结果,而二分查找法最多只需要32次(log40亿)就能找到结果。这个级别的数据,差距就比较可观了。

假设B一秒钟能猜10个数字,通过简单查询要猜4629(40亿/10 秒)天,而通过二分查找只需要4秒(log40亿/10 秒)。

有上面的例子可以看出,一个优秀的算法是多么的重要!

注意:log指的都是log2

大O表示法

大O表示法指出了算法有多快(O为操作数:Operations)。例如,假设列表包含n个元素。简

单查找需要检查每个元素,因此需要执行n次操作,使用大O表示法,

这个运行时间为O(n)。二分查找需要执行log n次操作,使用大O表示法的运行时间为 O(log n)。

关于大O表示法有以下几点需要注意:

  1. 大O表示法让你能够比较操作数,它指出了算法运行时间的增速,代表随着数据集的增加,算法所需时间的变化趋势。
  2. 大 O 表示法指出了最糟情况下的运行时间

下面按从快到慢的顺序列出了常见的5种大O运行时间:

  • O(log n),也叫对数时间,这样的算法包括二分查找。
  • O(n),也叫线性时间,这样的算法包括简单查找。
  • O(n * log n),这样的算法包括快速排序(一种非常快的 排序 算法)
  • O(n^2),这样的算法包括选择排序(一种非常慢的排序算法)。
  • O(n!),这样的算法包旅行商问题的解决方案-一种非常慢的算法。
  • 二分查找的速度比简单查找快得多。
  • O(log n)比O(n)快。需要搜索的元素越多,前者比后者就快得越多。
  • 算法运行时间是从其增速的角度度量的。
  • 算法运行时间用大O表示法表示。

以上所述就是小编给大家介绍的《算法快学笔记(一):算法入门》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

程序员面试宝典(第5版)

程序员面试宝典(第5版)

欧立奇、刘洋、段韬 / 电子工业出版社 / 2015-10 / 55.00

容提要 《程序员面试宝典(第5版)》是《程序员面试宝典》的第5 版,在保留第4 版的数据结构、面向对象、程序设计等主干的基础上,修正了前4 版近40 处错误,解释清楚一些读者提出的问题,并使用各大IT 公司及相关企业最新面试题(2014-2015)替换和补充原内容,以反映自第4 版以来两年多的时间内所发生的变化。 《程序员面试宝典(第5版)》取材于各大公司面试真题(笔试、口试、电话面试......一起来看看 《程序员面试宝典(第5版)》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具