算法导论-第一部分-读书笔记

àì夳堔傛蜴生んèń 2022-05-31 13:50 286阅读 0赞

\#工具

*  MarkDown数学公式
 *  [markdown 数学符号写法][markdown]
 *  [数学公式对应的markdown代码][markdown 1]
 *  [Cmd Markdown 公式指导手册][Cmd Markdown]
 *  [函数图像绘制工具][Link 1]
 *  [绘图工具][Link 2]：看着挺强大的，不光能绘制数学图像。（没用过）
 *  [对数在线计算器][Link 3]

\#小知识点  
1， Θ ( 1 ) \\Theta(1) Θ(1)  
假设 T(n) 是规模为 n 的一个问题的运行时间。如果规模足够小，例如某个常量 c，n <= c，则直接求解需要常量时间，我们将其写作 Θ ( 1 ) \\Theta(1) Θ(1)。

2，关于递归公式  
T(n) = T(n-1)：最大复杂度一般为 Θ ( n 2 ) \\Theta(n^2) Θ(n2)。因为递归公式的和为`n-1 + n-2 + n-3 ... 1`，高斯公式计算后为： n ( n + 1 ) / 2 n(n+1)/2 n(n\+1)/2，去掉低阶项和常数后， n 2 n^2 n2。

T(n) = aT(n/b) + f(n)：最大复杂度一般为 Θ ( n l g n ) \\Theta(nlgn) Θ(nlgn)

\#资料

*  [课后习题答案][Link 4]
 *  [初學者寫給初學者的演算法教學][Link 5]：非常棒的详解资料，有很多图例说明。把一个书上讲的很简略的内容，都说的非常详细。感觉像是对这本书的一个补充
 *  常用符号：∈ ∉ ⊂ ⊄ ⊆ ⊃ ⊇ ∪ ∩

\#TODO  
1，第5章 概率问题还没有看  
2，每种算法的改良算法都有什么？  
3，第7章思考题感觉有意思，可以看看  
4，看一下“卡特兰数”的定义，和实际解决的问题，有很多面试都问过。  
5，练习尾递归变成while。18.2 insert-nonfull 可以练习，还有其它章。  
6，平衡查找树（2-3-4 树）的特点，和其它树有什么区别。[平衡查找树（2-3-4 树）][2-3-4]  
[从2-3-4树谈到Red-Black Tree（红黑树）][2-3-4_Red-Black Tree]

*  [Catalan数（卡特兰数）][Catalan]：讲的基础
 *  [卡特兰数的初步学习][Link 6]：讲的基础。关于例子，讲了找零例子中，如果不按固定顺序的话，要乘N!。因为卡特兰数和动态规则中，元素的位置都是不变的。如果要位置不是固定的话，那就要在原先结果上，再乘以 N! 。因为 N 个元素的排列组合，就是从 N 个数中取一个，再从 N-1 个数中取一个，再从 N-2 个数中取一个，一起到 1，所以是 N!。
 *  [从《编程之美》买票找零问题说起，娓娓道来卡特兰数——兼爬坑指南][Link 7]
 *  [2012腾讯实习笔试中看到的Catalan数][2012_Catalan]

“卡特兰数”有两个公式，一个是递归的，可以用在程序上来写程序算法。还有一种是简单的公式，可以用来计算有多少种组合：(2n)! / ((n+1)! \* n!)

\#第一章  
\#\#练习  
\#\#\#\#1.2-2 假设我们正比较插入排序与归并排序在相同机器上的实现。对规模为n的输入，插入排序运行8n2步，而归并排序运行64nlgn步。问对哪些n值，插入排序优于归并排序？

所以有：8n^2 ≤ 64nlgn ⇒ n < 8lgn 需要解一下这个超越方程，  
编个程序很容易得到： 2 ≤ n ≤ 43  
（这个地方，就不要用算数的方式去解了，应该使用程序或计算器去解。因为超越方程很难解，像带有指数、对数、根号的计算式，最好都使用计算器去解）

\#\#\#\#1.2-3 n的最小值为何值时，运行时间为100n2的一个算法在相同机器上快于运行时间为2n的另一个算法？

原理同上题，可列出如下不等式：100n2 ≤ 2n 解这个不等式(代数法)，可求出最小的整数 n=15  
程序参考：[http://www.cnblogs.com/ghj1976/archive/2013/03/01/2938807.html][http_www.cnblogs.com_ghj1976_archive_2013_03_01_2938807.html]

\#\#\#思考题  
\#\#\#\#1-1（运行时间的比较）　假设求解问题的算法需要f(n)毫秒，对下表中的每个函数f(n)和时间t，确定可以在时间t内求解的问题的最大规模n。  
再说一下这个题，下面 lgn、sqrt(n)、n 等都是一个 f(n)函数。当 n 最大为多大时，1秒、1分钟、1小时等时间可以处理完。因为 f(n) 单位为毫秒，所以我们需要把1秒、1分钟、1小时也变成毫秒单位。  
拿 1秒钟内，处理 lgn 这个函数来举例：  
1秒钟为1000毫秒，lgn 这个函数的执行时间为 f(n) 毫秒，也就是说，f(n) 时间不能比 1000毫秒 大，因为如果比 1000毫秒大的话，1000毫秒之内就处理不完了。所以，计算式为：

> 1000/(lgn) <= 1  
> 1000 <= lgn  
> 2^1000 = n

具体结果如下：

> 这个结果，也变相说明了“每种函数的复杂度”。从上到下，复杂度越来越高。  
> 例如：如果一个算法时间复杂度是 lgn 函数，1秒钟时间内，算法中的变量 n 可以为 2^1000 这么大。但如果算法时间复杂度是 n^2 函数，算法中的变量 n 只能为 32 这么大。

各种函数的图如下：  
![这里写图片描述][SouthEast]

注意：  
1，lgn 和 $ \\sqrt n $。在 n 大约 <= 16 时，他们之间的时间是相互交错的。

*  $ 0 < n < x (x \\approx 3 $)： lgn < $ \\sqrt n $
 *  $ x (x \\approx 3  ) < n < y ( ) < n < y ( )<n<y( y \\approx 16 $)： $ \\sqrt n $ < lgn
 *  $ y (y \\approx 16 $) < n < 无穷大)： lgn < $ \\sqrt n $

2，$ 2 ^ n $ 在最开始一定范围内小于 $ n ^ 3  ， 但 n 足 够 大 时 （ 大 约 1000 以 上 的 某 个 数 字 ） ， ，但 n 足够大时（大约 1000 以上的某个数字）， ，但n足够大时（大约1000以上的某个数字）， 2 ^ n > n ^ 3 $

\#第三章  
\#\#2.2 分析算法  
\#\#\#插入排序  
\#\#\#\#1，插入排序内容  
主要思想：

*  从第2个元素开始判断，是否比前一个数据小，如果小的话，把前一个数据向后移动一位。
 *  直接没有比当前数据小的时候，把当前数据放到比较指针的位置

最大复杂度：O( n 2 n ^ 2 n2)  
最小复杂度 ：O( n n n)  
排序空间使用：原址  
使用场景：todo

\#\#\#\#2，算法分析  
下图是插入算法的代码和执行次数：  
![这里写图片描述][SouthEast 1]

注意：  
1，循环头（for while）执行次数是 n，循环体执行次数要比循环头少1次，所以循环体执行次数是 n - 1。

下面是根据上面的图，统计的时间公式：  
![这里写图片描述][SouthEast 2]

![这里写图片描述][SouthEast 3]

\#\#2.3 设计算法  
\#\#\#归并排序  
\#\#\#\#1，归并排序内容  
主要思想：

*  把数据不断拆分，分成单位是1的数据
 *  然后使用"合并有序队列"方法，把数据不断合并

最大复杂度：O( n l g n nlgn nlgn)  
最小复杂度 ：todo  
排序空间使用：非原址  
使用场景：todo

![这里写图片描述][SouthEast 4]

\#\#\#\#2，算法分析  
归并排序实际上是使用了“分治算法（divide and conquer）”，分治算法的时间复杂度公式如下：  
![这里写图片描述][SouthEast 5]

1，下面说一下上面公式的内容：

*  T(n)：规模为 n 问题的运行时间。
 *   Θ ( 1 ) \\Theta(1) Θ(1)：如果规模足够小，例如某个常量 c，n <= c，则直接求解需要常量时间，我们将其写作 Θ ( 1 ) \\Theta(1) Θ(1)。在这里，当分到不能再分了，分到了最小规模时，这个时间就是 Θ ( 1 ) \\Theta(1) Θ(1)。
 *  a 和 b：把问题分解成 a 个子问题，每个子问题的规模为 b 。（对于归并排序，a 和 b 都是 2，但在其它一些分治算法中 a <> b）。
 *  aT(n/b)：为了求规模为 n/b 的子问题，需要 T(n/b) 时间，所以对于 a 个子问题，需要 aT(n/b) 这么多时间。
 *  D(n)：分解问题的时间。（D 应该是是 Divide 的意思）
 *  C(n)：合并子问题的解的时间。（C 应该是 combine 的意思）

2，分治算法的分析步骤  
分治算法时间分析一共分3步：  
**分解(Divide)**：分析步骤只是计算数组中间的位置，需要常量时间，所以 D(n) = $\\Theta(1) $  
**解决(Conquer)**：我们递归地求两个规模为2的子问题，所以运行时间为 2T(n/2)  
**合并(Combine)**：一个具有 n 个元素的数组，合并需要$\\Theta(n) $时间，所以 C(n) = $\\Theta(n) $。

公式又可以变为：  
![这里写图片描述][SouthEast 6]

> D(n) 和 C(n) 相加时，就是把$\\Theta(n)  和 和 和\\Theta(1)  相 加 。 相 加 的 和 是 n 的 一 个 线 性 函 数 ， 即 相加。相加的和是 n 的一个线性函数，即 相加。相加的和是n的一个线性函数，即\\Theta(n) $。

3，证明 T(n) =  Θ ( n l g n ) \\Theta(nlgn) Θ(nlgn)  
分治算法的T(n)，其实就是 Θ ( n l g n ) \\Theta(nlgn) Θ(nlgn)。但为什么是 Θ ( n l g n ) \\Theta(nlgn) Θ(nlgn)呢？下面我们就来证明一下。  
首先，我们把上面的公式再重写一下：  
![这里写图片描述][SouthEast 7]

> c 代表：规模为 1 的问题所需要的时间 + 分解时间 + 合并数组时间

下面看一下递归树的分解，和时间计算：  
![这里写图片描述][SouthEast 8]

\#\#\#\#\#（1）关于每层的时间  
我们看一下图(d)，第一层的时间为 cn，第二层的时间为 cn/2 + cn/2 = cn，第三层的时间为 cn/4 + cn/4 + cn/4 + cn/4 = cn，下面的层以此类推。  
我们来推理一下上面的结果。一般来说，顶层之下的第 i 层，就会有  2 i 2 ^ i 2i 个节点，每个节点的时间为  c n / 2 i cn/2^i cn/2i (1层为 cn/2，2层为 cn/4，注意上面说是顶层之下，所以 cn/2 那层是第1层)。所以，顶层之下第 i 层的时间为  2 i ∗ c n / 2 i = c n 2^i \* cn/2^i = cn 2i∗cn/2i=cn。

\#\#\#\#\#（2）关于层数  
每层的时间我们知道了，那么有多少层呢？假设最终分解成 8 个节点，那么总共有会有 4 层。顶层之下，

*  第 1 层有 2 个节点，lg2 = 1（2 为节点数， 1为层数）
 *  第 2 层有 4 个节点，lg4 = 2（4 为节点数， 2为层数）
 *  第 3 层有 8 个节点，lg8 = 3（8 为节点数， 3为层数）

所以，总层数为 lgn + 1(1这个常量可以省略)

\#\#\#\#\#（3）关于总的时间  
既然“层数”和“每层的时间”我们都知道了，那么总的时间也就知道了，总的时间为：cn \* (lgn + 1) = cnlgn + cn

忽略了低阶项和常量后，最后的时间为： Θ ( n l g n ) \\Theta(nlgn) Θ(nlgn)

\#\#练习  
我们可以把插入排序表示为如下的一个递归过程。为了排序A［1…n］，我们递归地排序A［1…n-1］，然后把A［n］插入已排序的数组A［1…n-1］。为插入排序的这个递归版本的最坏情况运行时间写一个递归式。

解答：  
模仿下图的公式：  
![这里写图片描述][SouthEast 7]

我们的公式，把 2T(n/2) 换成 T(n-1)，下面我们来计算层数和每层的时间。  
关于每层的时间：  
第一层为 cn，第二层为 c(n-1)，第三层为 c(n-2)，以此类推，最后一层为 c。

关于层数：  
从 cn 到 c(n-1) 到 c(n-2) … c，一共有 n + 1 层。

所以总时间为，每层时间的和，也就是 cn + c(n-1) + c(n-2) … c。如果把 c 去掉，也就是 0 + 1 + 2 + 3 + … n，也就是高斯公式 n(n+1)/2 =  n 2 / 2 + n / 2 = n 2 n^2/2 + n/2 = n^2 n2/2\+n/2=n2（最后去掉低阶项）

\#第三章  
\#\#3.1 渐进记号

*   O O O：最大复杂度，是一个函数的上界。相当于“<=”。
 *   Ω \\Omega Ω：最小复杂度，是一个函数的下界。相当于“>=”。
 *   Θ \\Theta Θ：把一个公式的低阶项去掉，并忽略前面的常数因子。 Θ \\Theta Θ可以看成是：  T ( n ) = O ( f ( n ) ) 且 T ( n ) = Ω ( f ( n ) ) ， 则 称 T ( n ) = Θ ( f ( n ) ) T(n)=O(f(n))且 T(n) =\\Omega (f(n))，则称 T(n) =\\Theta (f(n)) T(n)=O(f(n))且T(n)=Ω(f(n))，则称T(n)=Θ(f(n))。相当于“=”。
 *   o o o：类似于 O O O，但是没有“=”，所以相当于“<”。
 *   ω \\omega ω：类似于 Ω \\Omega Ω，但是没有“=”，所以相当于“>”。

\#第四章  
4.1 最大子数组问题  
当以价格变化为基础，求最大子数组时，最大子数组可能存在 3 种位置：

*  位于子数组A\[low…mid\]中
 *  位于子数组A\[mid…high\]中
 *  跨越了中心点，在 low <= i <= mid < j <= high

当跨越了中心点时，求最大子数组时，只需要从中心点 向左 和 向右 分别求出最大子数组，然后相加就可以了。  
为什么从中间点开始，向左 和 向右 进行求最大子数组呢，为什么不是“从左和右，分别向中间点”求最大子数组呢？因为第3种位置的情况是“跨越了中心点”的情况，从两边向中心点找最大子数组的话，可能两边找出的最大子数组位置是连不上的。连不上的话，就等于位置1和2的情况了。

todo:看看其它的求股票最大收益的算法

\#第五章  
\#\#5.3 随机算法  
随机算法的作用是，防止总是出现最差情况，把最差情况变成平均情况。  
\#\#\#随机排序数组  
![这里写图片描述][SouthEast 9]

\#\#\#原址随机排序  
![这里写图片描述][SouthEast 10]

[markdown]: http://blog.csdn.net/bone_ace/article/details/46400975
[markdown 1]: http://blog.csdn.net/sanqima/article/details/48576361
[Cmd Markdown]: https://www.zybuluo.com/codeep/note/163962
[Link 1]: https://zh.numberempire.com/graphingcalculator.php
[Link 2]: https://www.desmos.com/calculator
[Link 3]: https://www.99cankao.com/algebra/logrithm.php
[Link 4]: https://www.kancloud.cn/windmissing/algorithms-my-answer/115239
[Link 5]: http://alrightchiu.github.io/SecondRound
[2-3-4]: http://www.cnblogs.com/gaochundong/p/balanced_search_tree.html
[2-3-4_Red-Black Tree]: http://blog.csdn.net/v_JULY_v/article/details/6531399
[Catalan]: http://blog.sina.com.cn/s/blog_6aefe4250101asv5.html
[Link 6]: https://www.cnblogs.com/code-painter/p/4417354.html
[Link 7]: https://www.cnblogs.com/wuyuegb2312/p/3016878.html
[2012_Catalan]: http://blog.csdn.net/jtlyuan/article/details/7440591
[http_www.cnblogs.com_ghj1976_archive_2013_03_01_2938807.html]: http://www.cnblogs.com/ghj1976/archive/2013/03/01/2938807.html
[SouthEast]: /images/20220531/31177a1475554ab999b116e755195595.png
[SouthEast 1]: /images/20220531/6fa5eb3f37fc425eb7c4cc847e2e39eb.png
[SouthEast 2]: /images/20220531/7004015332bb4419b417fa16d9a56894.png
[SouthEast 3]: /images/20220531/f1430bccbf304681a66c87bb30d2373b.png
[SouthEast 4]: /images/20220531/9f8a7cf2b40542e09ae7b6938a258f96.png
[SouthEast 5]: /images/20220531/b73de5b4dabc4f1285c410bcba4aa7aa.png
[SouthEast 6]: /images/20220531/b620c8d91b5d4faf820804c9d8a38e36.png
[SouthEast 7]: /images/20220531/d173a626f82c4c908ab55f90eb323265.png
[SouthEast 8]: /images/20220531/01d205ac38fb47bbac319af8ffa41f04.png
[SouthEast 9]: /images/20220531/72642e66aa0a41b9883472d4b3010382.png
[SouthEast 10]: /images/20220531/350acce06b3547389072d17e7b65f0df.png