20220526数据结构绿皮书读书笔记

7 搜索

7.1 简介

记录(record)的一小部分称之为键(key)，我们允许有一个以上的record包含相同的key或没有record包含指定的key

external搜索和internal搜索，区分的是内存的里和外

在链表上搜索并不会有很高的效率，后面默认讨论的是基于数组的实现列表，这个列表应该满足最小要求：
1.每个record都有关联的key
2.key之间可以被相对或绝对的比较
3.record之间可以被比较，或者可以被转成key比较

7.2 顺序搜索

最简单的过程，从开始的元素逐一比较
平均比较次数 (1+2+…+n)/n–>(n+1)/2

7.3 二分搜索

有序数据集上，pivot入中位，看是往前还是往后
容易写错的是，比较完成的中位如果不是要找的，需要丢掉，pivot需要+1或者-1后再继续二分

7.4 比较/搜索/决策树

每个节点代表一次key的比较，节点的值放入被比较key的index，树的树杈连接的代表下次可能的比较位置，树杈上标明条件，叶子节点放置搜索终止状态，失败或者是成功。叶子节点有时也被乘坐终节点或者外部节点，其余节点称作树的内部节点

压缩画法，可以使用二叉树来画出三路比较，叶子节点均为失败，非叶子节点为查找成功

二叉树&完全二叉树，有一堆公式，可以现用现查。但一定要知道什么能算得出来什么算不出来，看高数基础了
吐个槽，感觉玩算法就是拼数学水平，人家数学好的直接知道公式和模板，不知道的我们只能傻乎乎的模拟计算结果

说明下后面为啥可能出现log2(n)，因为比较次数是树的高度，二叉树的高度刚好和n有对数关系，所以会出现很多以2为底的log，一般如果写lg数学上是以10为底的，但这里底数一般是2

二叉搜索比较次数：(2(n+1)/n)*lg(n+1)-3

7.5 下界

1.打磨程序，俗称优化
2.寻找任意搜索算法
能否找到一个再最坏和平均情况下比较次数都少于二分搜索的算法呢？答案是不可能的，数学证明略，总之为了从n个值里搜索1个指定值是存在数学上的下界的
3.通过观察搜索树可以得知
假设T是一个有k个叶子节点的二叉树，那么它的高度h一定满足h ≥ lgk向上取整，external路径长度E(T)满足E(T) ≥ k*lgk h和E(T)的最小值出现在所有叶子节点在同一层或者在两个相邻的层
4.结论
lgn向上取整 + 1
5.其他搜索方式
当基于比较进行搜索的时候，无法快于上述情况，但不是所有的搜索都是基于比较key进行的，举个例子：数组里放着一堆数字刚好是0~n-1，我们知道index=x的情况下可以直接取出index=x的值而不需要搜索。
这种搜索叫做插值搜索，我们假设所有的key都是数字或者就是信息本身，比如单词可以被记录为数字。同时这种方法要求数据均匀分布
当我们想从500页的书中翻到345的时候，你会直接取寻找三分之二的位置，大概就和这个原理类似

7.6 函数的阶、级数、无穷级数

高数概念：函数的阶，函数之间的同阶（极限比为0）、等阶（为非零有穷）、高阶（为无穷）

算这玩意需要求极限，略

直接记结论如下
O(g(n))表示f(n)的阶小于或等于g(n)的阶，极限比为有穷
o(g(n))表示f(n)的阶严格小于g(n)的阶，极限比为0
Theta(g(n))表示f(n)与g(n)的阶相等，极限比为非零且有穷
Omega(g(n))表示f(n)的阶大于或等于g(n)的阶

按我理解通常来说寻找高阶的函数比寻找低阶函数要容易口算，因此描述一个算法的时空复杂度通常会用大O，O(n)表示这个算法的时空复杂度函数f(x)的阶小于或等于f(x)=n

明天继续第8章 排序
mark 目前是317页 ，pdf是334页