Simple Sidebar
The starting state of the menu will appear collapsed on smaller screens, and will appear non-collapsed on larger screens. When toggled using the button below, the menu will change.
Make sure to 能在K线当中看出来什么？ keep all page content within the #page-content-wrapper . The top navbar is optional, and just for demonstration. Just create an element with the #sidebarToggle ID which will toggle the menu when clicked.
tail -f 查找关键字_九种查找算法
weixin_39941721 于 2020-11-20 15:44:37 发布 2376 收藏 2
时间、空间复杂度比较
| 查找算法 | 平均时间复杂度 | 空间复杂度 | 查找条件 |
|---|---|---|---|
| 顺序查找 | O(n) | O(1) | 无序或有序 |
| 二分查找(折半查找) | O(log2n) | O(1) | 有序 |
| 插值查找 | O(log2(log2n)) | O(1) | 有序 |
| 斐波那契查找 | O(log2n) | O(1) | 有序 |
| 哈希查找 | O(1) | O(n) | 无序或有序 |
| 二叉查找树(二叉搜索树查找) | O(log2n) | ||
| 红黑树 | O(log2n) | ||
| 2-3树 | O(log2n 能在K线当中看出来什么？ - log3n) | ||
| B树/B+树 | O(log2n) |
1 顺序查找
算法思路：
代码：
运行结果：
查找成功 查找失败
2 二分查找(折半查找)
算法思路：
说明：
在做查找的过程中，如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。
代码：
运行结果：
查找成功 没有查找到
3 插值查找
算法思路：
说明：
- 插值查找是基于折半查找进行了优化的查找方法。
- 当表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能要比折半查找要好得多。
代码：
运行结果：
运行结果
4 斐波那契查找
算法思路：
说明：
low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。
代码：
运行结果：
47的位置为5
5 哈希查找
哈希表：
哈希函数：
算法思路：
- 用给定的哈希函数构造哈希表；
- 根据选择的冲突处理方法(常见方法：拉链法和线性探测法)解决地址冲突；
- 在哈希表的基础上执行哈希查找；
代码：
6 二叉树查找
算法思路：
- 若b是空树，则搜索失败：
- 若x等于b的根节点的数据域之值，则查找成功：
- 若x小于b的根节点的数据域之值，则搜索左子树：
- 查找右子树。
代码：
7 2-3树
算法思路:
2-3 树中查找键为H的节点 2-3 树中查找键为B的节点
代码：
8 红黑树
理解红黑树一句话就够了：红黑树就是用红链接表示3-结点的2-3树。
2-3树转红黑树
为什么使用红黑树：
- 红黑树是一种平衡树，他复杂的定义和规则都是为了保证树的平衡性。如果树不保证他的平衡性就是下图：很显然这就变成一个链表了。
- 保证平衡性的最大的目的就是降低树的高度，因为树的查找性能取决于树的高度。所以树的高度越低搜索的效率越高！
- 这也是为什么存在二叉树、搜索二叉树等，各类树的目的。
红黑树性质：
- 每个节点要么是黑色，要么是红色。
- 根节点是黑色。
- 每个叶子节点(NIL)是黑色。
- 每个红色结点的两个子结点一定都是黑色。
- 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
算法思路：
红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。
代码：
9 B树/B+树
- 定义任意非叶子结点最多只有M个儿子；且M>2；
- 根结点的儿子数为[2, M]；
- 除根结点以外的非叶子结点的儿子数为[M/2, M]； 能在K线当中看出来什么？
- 每个结点存放至少M/2-1(取上整)和至多M-1个关键字；(至少2个关键字)
- 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]； 能在K线当中看出来什么？ 能在K线当中看出来什么？
- 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的 子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
- 所有叶子结点位于同一层；
如：(M=3)
算法思路：
- 关键字集合分布在整颗树中；
- 任何一个关键字出现且只出现在一个结点中；
- 搜索有可能在非叶子结点结束；
- 其搜索性能等价于在关键字全集内做一次二分查找；
- 自动层次控制；
代码：
B+树：
- 非叶子结点的子树指针与关键字个数相同；
- 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树, B树是开区间
- 为所有叶子结点增加一个链指针;
- 所有关键字都在叶子结点出现；
1
iPad Pro 2020 的实际体验如何？值得入手吗？
最新对比跑分，Mac为低配版
目前，苹果唯一一款带Face ID的“电脑”
我这款是iPad Pro 11 英寸 512G，视频更新了下加了新内容
外形如何？会不会弯
会不会弯？材质目前体验是一样的还是。很薄，弯的话真的个人感觉还好，还是平时带带套比较稳妥。因为iPad Air也会弯呀。是薄的就可能会弯的。预算够的当然再买个Apple care就更好了，随便裸奔，随便浪。
正面对比，能看出哪个是新款不？不可能看出来啦 边框 摄像头对比 背面对比 C口 数据线 摄像头特写
新款性能到底如何？
2018 iPad Pro 11英寸 2020 iPad Pro 11英寸
这是为啥呢？新款性能还不如旧款吗？
3.27更新:老外最新消息，之前的A12X GPU7核说是其实也是8核，被Apple自己封印内力，Apple NB！
摄像头的提升作用到底有多少？
这次iPad Pro升级最值得的地方是哪里？
图取自Apple
图取自Apple 官方视频
ttweixiao9999
不要轻视他人,每个人都有我们值得学习的地方 Don't look down on others, everyone has something to learn from
vscode 运行和调试 javascript 代码 (vscode run and debug javascript code)
初次正式要写 javascript 相关的代码,想要用 vscode 直接编译 js 代码,但是发现没有那么简单,需要配置好 launch.json 文件,现已经在vscode上编译过去并且可以调试 javascript 代码,总结了两种方法,分享给大家.
方法一: 在 js 后缀文件中写 javascript 代码. 能在K线当中看出来什么？
(1). 需要安装 nodejs (在Bing搜索中输入 nodejs, 找到nodejs官网,然后找到适合你电脑配置的安装包进行下载安装,最后要输入 node -v 和 npm -v 检验是否安装成功)
(2). （可选项，可以安装下看下结果）如果你想直接看结果，不想debug调试也可以安装 vscode 扩展包: Code Runner 运行 javascript 代码
2. 新建一个 js 后缀的文件,如 hello_world.js ,输入以下内容:
注意这里的第 11 能在K线当中看出来什么？ 行的文件名称要改成你自己定义的文件名称,其中的 workspaceRoot 表示当前文件路径.
再按下 F5 的时候,记得配置文件一定要选择名为 Launch (和上面的name同名) 的那个配置文件运行,配置了 launch.json 文件,你还可以在 js 文件中打上断点进行调试.如下图所示
能在K线当中看出来什么？ 
（如果你debug成功请忽略这一段话）如果你第一种和第二种方法你都成功了（说明你的代码没有问题），但是使用第三种方法进行 debug 的时候一直不能显示 debug 效果，什么都没有显示和反应，那么可以试下在 setting.json 文件中加上以下语句应该就没问题了： "debug.javascript.能在K线当中看出来什么？ 能在K线当中看出来什么？ usePreview": false, 参考资料：https://github.com/microsoft/vscode-js-debug/issues/643
方法二: 在 html 后缀文件中写 javascript 代码.
(1) 安装 chrome 浏览器(做前端开发这是通用浏览器)
(2) 安装 vscode 扩展包: Debugger for chrome 和 open in browser
(3) File -> Preferences -> Settings, 输入 breakpoints，找到 Debug: Allow Breakpoints Everywhere，勾上允许在任何文件设置断点（这样才可以在html文件中设置断点）
2. 新建一个 html 能在K线当中看出来什么？ 能在K线当中看出来什么？ 后缀的文件,如 a.html ,输入以下内容:
(1) 按下 F5 运行并且调试代码,这里主要涉及到 launch.json 文件的配置,先点击 Run -> Open Configurations, 输入以下内容
然后在 能在K线当中看出来什么？ script 的代码部分打上断点,按下 F5 , 点击 Try it 按钮,你可以看到中间结果了,如下图所示
(2) 鼠标右键点击 Open in Other Browsers, 选择其中 一个浏览器就可以看到结果,再点击按钮出现的网页中的 Try it 按键,就可以调用 script 中 js 的代码的结果. 这里,你也可以在vscode中设置你的默认浏览器,那么你就可以选择Open 能在K线当中看出来什么？ in Default Browers, 在默认的浏览器中打开, 或者按下快捷键 Alt + B 查看结果. (这种方法不能调试,并且这种方法只能在配置好launch.json后再按下F5之后才可以使用)
(备注: vscode 默认浏览器的设置, File -> Preferences -> Settings, 输入 default browser , 找到 Open-in-browser : Default , 我这里是输入了 : Google Chrome )