wuxiaosi0 2019-07-01
简单数据结构(必须理解和掌握)
复杂数据结构
数组和列表: 最常用的数据结构
链表: 如何通过它们克服数组的不足,
二分查找是搜索算法中的一种,用来搜索有序数组
二分查找:是一种简单算法,其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要
查找的元素包含在列表中,二分查找返回其位置;否则返回null
。
/** * 函数binarySearch接受一个有序数组和一个元素。 如果指定的元素包含在数组中, 这个 函数将返回其位置。 你将跟踪要在其中查找的数组部分—— 开始时为整个数组。 */ const binarySearch = (list, item) => { // 数组要查找的范围 // low、high用于跟踪要在其中查找的列表部分 let low = 0 let high = list.length - 1 while(low <= high) { // 只要范围没有缩小到只包含一个元素 const mid = Math.floor((low + high) / 2) const guess = list[mid] // 找到中间的元素 if(guess === item) { // 找到元素 return mid } if(guess > item) { // 猜测的数大了 high = mid - 1 } else { // 猜测的数小了 low = mid + 1 } } return null } const myList = [1, 3, 5, 7, 9] console.log(binarySearch(myList, 3)) console.log(binarySearch(myList, -1))
const binarySearch = (list, item, low, hight) => { let arrLength = list.length while (low <= high) { let mid = Math.floor((low + high) / 2) let guess = list[mid] if( guess === item ) { return mid } else if (guess > item) { high = mid - 1 list = list.slice(0, mid) return binarySearch(list, item, low, high) } else { low = mid + 1 list = list.slice(low, arrLength) return binarySearch(list, item, low, high) } } return null } const createArr = (n) => Array.from({length: n}, (v, k) => k + 1) const myList = createArr(100) let low = 0 let high = myList.length - 1 console.log(binarySearch(myList, 3, low, high)) console.log(binarySearch(myList, -1, low, high))
二分查找的运行时间为对数时间(或log时间)。
如果列表包含100个元素,最多要猜7次;如果列表包含40亿个数字,最多
需猜32次。
即: 2的7次方 = 100
简单查找时间是 y= ax 的线性方方程
所以很容易得出结论
随着元素数量的增加(x增加),二分查找需要的时间(y)并不多, 而简单查找需要的时间(y)却很多。
因此,随着列表的增长,二分查找的速度比简单查找快得多。
为检查长度为n的列表,二分查找需要执行log n次操作。使用大O表示法,
这个运行时间怎么表示呢?O(log n)。一般而言,简单算法的大O表示法像下面这样
大O符号中指定的算法的增长顺序
以下是一些最常用的 大O标记法
列表以及它们与不同大小输入数据的性能比较。
快速排序
——一种速度较快的排序算法。选择排序
——一种速度较慢的排序算法快排和二分查找都基于一种叫做「分治」的算法思想,通过对数据进行分类处理,不断降低数量级,实现O(logN)
(对数级别,比O(n)
这种线性复杂度更低的一种,快排核心是二分法的O(logN)
,实际复杂度为O(N*logN)
)的复杂度。
快排大概的流程是:
简单的讲如果旅行者要去5个城市,先后顺序确定有5*4*3*2*1 = 120种排序。(这种排序想想高中时候学到过的排序知识)
推而广之,涉及n个城市时,需要执行n!(n的阶乘)次操作才能计算出结果。因此运行时间
为O(n!),即阶乘时间。除非涉及的城市数很少,否则需要执行非常多的操作。如果涉及的城市
数超过100,根本就不能在合理的时间内计算出结果——等你计算出结果,太阳都没了。
这种算法很糟糕!,可别无选择。这是计算机科学领域待解的问题之一。对于这个问题,目前还没有找到更快的算法,有些很聪明的人认为这个问题根本就没有更巧妙的算法。
面对这个问题,我们能做的只是去找出近似答案。
最后需要指出的一点是,高水平的读者可研究一下二叉树
关于二叉树,戳这里: 数据结构与算法:二叉树算法
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
算法图解
JavaScript 算法与数据结构
https://github.com/egonSchiel...
【算法】时间复杂度
【算法】空间复杂度
InterviewMap 时间复杂度
https://github.com/trekhleb/j...
每周一练 之 数据结构与算法(Stack)