算法学习

又开了一个系列的新坑,上个月买了两本书一本是《重构》另外一本就是今天我要讲的《图解算法》,今天这篇就算开个头。当做我自己的学习日记。我会把我自己在学这本书中遇到的知识点总结起来,供大家(我自己)使用。

需要具备的知识

基本的代数知识,比如 1 + 1 = 2。

运行时间

一般而言,应选择下率最高的算法,以最大限度的减少运行的时间或者空间。

O(大写的o)表示法

她表示的是让你能够比较操作数,而不是以秒为单位的速度。
灵魂画家

补充

算法的速度指的并非是时间,而是操作式的增速。
O(log n)比O(n)快,当需要搜索的元素越多时,前者比后者块的越多。

二分查找

二分查找是一种算法,其输入是一个有序的元素列表。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回null。


我们一般查字典的时候一般是先从目录的拼音开始查,找到具体的字之后再翻到具体的页数。要是经常查字典的人会随便翻一页看页码上面的拼音第一个字母与自己想查的的那个字的拼音比较。来决定往前翻还是往后翻。确定拼音的第一个字母之后再比较第二个字母以此类推。就能找到你想查的那个字(如果不会读,当我没说)。其实这也算是算法,就是二分法的基本原理。


一般来说,对于包含n个元素的列表,用二分查找最多需要log2n(以二为底n的对数),用二分法查找最多需要log2n步,而简单查找最毒需要n步。
实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
let arr = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
function dichotomy(arr, findNum) {
let index = Math.floor(arr.length / 2)
let beforeIndex = 0// 记录上次index的位置
let count = 0 //循环次数
while (true) {
count++
if (arr[index] > findNum){ // 中间值大于要找的数
beforeIndex = index
index = Math.floor(index / 2)
} else if(arr[index] < findNum) { // 中间值小于要找的数
if (beforeIndex === 0) { // 判断是不是第一次循环
index = Math.floor((index + arr.length)/2)
} else {
index = Math.floor((index + beforeIndex)/2)
}
} else {
return `数组下标${index},循环次数${count}.`
}
}
}
dichotomy(arr,5) //数组下标4,循环次数6.

动态规划

  1. 确定问题
  2. 拆分问题
  3. 拆分问题求解

感谢您的阅读。 🙏