算法设计与分析(屈婉玲)视频笔记day2

墨蓝 2024-03-27 16:45 45阅读 0赞

## **序列求和的方法** ##

### **数列求和公式** ###

#### **等差、等比数列与调和级数** ####

![954096aea6d0680ae8b9f6c3b6d9de85.png][]

#### **求和的例子** ####

![b472fab84eb04d84c595df75e7817bac.png][]

#### **二分检索算法** ####

![ca39918f656f434c0541419a717b264b.png][]

#### **二分检索运行实例** ####

![0d9efcb79fa29ec4cc29770be33f61d7.png][]

##### **2** ***n*** **+1个输入** #####

![a4df46bc08dbae12932bf3e743b28334.png][]

##### **比较** ***t*** **次的输入个数** #####

![8b250a7d9cd80707c0322d1b980651a9.png][]

#### **二分检索平均时间复杂度** ####

![98f29b1b81a684efdf7d568ede2cd429.png][]

#### **估计和式上界的放大法** ####

![9d73dfa57a89b22b735710674fbcf5cd.png][]

##### **放大法的例子** #####

![b9434a4c33d8791e206867e07d07e515.png][]

#### **估计和式渐近的界** ####

![54bffbb92a058b9ba2d776420068fca8.png][]

#### **估计和式渐近的界** ####

![1013ca2c3ef95baf184eab4e63efc8b8.png][]

#### **小结** ####

• **序列求和基本公式：**

**等差数列**

**等比数列**

**调和级数**

• **估计序列和：**

**放大法求上界**

**用积分做和式的渐近的界**

• **应用：计数循环过程的基本运算次数**

## **递推方程与算法分析** ##

### **递推方程** ###

![0b2c8c0c1f6ed94e2e106288eec748ac.png][]

### **递推方程的例子** ###

![2ae850fdd922410cf6aa84a585b115f1.png][]

### **Fibonacci数的存在** ###

![b51f27bb95a817c952ef219488282773.png][]

### **Hanoi塔问题** ###

![ce9fc4dfebe85e992d6feba880f40c8f.png][]

### **递归算法** ###

![8d1f977a6e0c1c43c48e6288580c21ee.png][]

#### **分析算法** ####

![f85ec48312ebaef80b313ddbbecac0db.png][]

### **插入排序** ###

![420d2956bf3aef1a56e3aaf25accebfd.png][]

#### **最坏情况下时间复杂度** ####

**插入排序：**

**设基本运算是元素比较，对规模为** ***n***

**的输入最坏情况下的时间复杂度** ***W*** **(** ***n*** **)**

***W*** **(** ***n*** **)=** ***W*** **(** ***n*** **-1)+** ***n*** **-1** ***W*** **(1)=0**

**解为** ***W*** **(** ***n*** **) =** ***n*** **(** ***n*** **-1)/2**

### **小结** ###

•**递推方程的定义及初值**

•**递推方程与算法时间复杂度的关系**

**Hanoi塔的递归算法 插入排序的迭代算法**

## **迭代法求解递推方程** ##

**迭代法**

•**不断用递推方程的右部替换左部**

•**每次替换，随着** ***n*** **的降低在和式中**

**多出一项**

•**直到出现初值停止迭代**

•**将初值代入并对和式求和**

•**可用数学归纳法验证解的正确性**

### **Hanoi 塔算法** ###

![ff03c660056545ba39ed9b3e1cc2f72a.png][]

### **插入排序算法** ###

![65c857379b28cdc1b51ab347d9dafb7f.png][]

### **换元迭代** ###

•**将对** ***n*** **的递推式换成对其他变元** ***k*** **的递推式**

•**对** ***k*** **直接迭代**

•**将解 (关于** ***k*** **的函数) 转换成关于** ***n*** **的函数**

### **二分归并排序** ###

**MergeSort (** ***A*** **,** ***p*** **,** ***r*** **)**

**输入：数组** ***A*** **\[** ***p*** **…** ***r*** **\]**

**输出：按递增顺序排序的数组** ***A***

**1. if** ***p*** **<** ***r***

**2. then** ***q*** **** **(** ***p+r*** **)/2** ****

**3. MergeSort (** ***A*** **,** ***p*** **,** ***q*** **)**

**4. MergeSort (** ***A*** **,** ***q*** **+1,** ***r*** **)**

![3fc670e11783f6ab6d6035d4d3a8455c.png][]

### **换元** ###

**假设** ***n*** **=2** ***k*** **,** **递推方程如下：**

***W*** **(** ***n*** **)=2** ***W*** **(** ***n*** **/2)+** ***n*** **** **1**

***W*** **(1)=0**

**换元：**

***W*** **(2** ***k*** **) = 2** ***W*** **(2** ***k*** **-1** **) + 2** ***k*** **** **1**

***W*** **(0) = 0**

### **迭代求解** ###

![bd0ecae654f6d2d9eb4c956487668a3a.png][]

### **解的正确性-归纳验证** ###

**证明** **:** **下述递推方程的解是** ***W*** **(** ***n*** **)=** ***n*** **(** ***n*** **** **1)/2**

***W*** **(** ***n*** **)=** ***W*** **(** ***n*** **** **1)+** ***n*** **** **1**

***W*** **(1)=0**

**方法：数学归纳法**

**证** ***n*** **=1** **，** ***W*** **(1)=1** **** **(1** **** **1)/2 = 0**

**假设对于** \***n ,** \***解满足方程，则**

***W*** **(** ***n*** **+1)**

**=** ***W*** **(** ***n*** **)+** ***n*** **=** ***n*** **(** ***n*** **** **1)/2 +** ***n***

**=** ***n*** **\[(** ***n*** **1)/2+1\] =** ***n*** **(** ***n*** **+1)/2**

### **小结** ###

**迭代法求解递推方程**

• **直接迭代，代入初值，然后求和**

• **对递推方程和初值进行换元，然**

**后求和，求和后进行相反换元，**

**得到原始递推方程的解**

• **验证方法——数学归纳法**

## **差消法化简高阶递推方程** ##

### **快速排序** ###

• **假设** ***A*** **\[** ***p*** **…** ***r*** **\]** **的元素彼此不等**

**以首元素** ***A*** **\[1\]** **对数组** ***A*** **\[** ***p…r*** **\]** **划分** **,** **使得：**

**小于** ***x*** **的元素放在** ***A*** **\[** ***p*** **…** ***q*** **** **1\]**

**大于** ***x*** **的元素放在** ***A*** **\[** ***q*** **+1…** ***r*** **\]**

• **递归对** ***A*** **\[** ***p*** **…** ***q*** **** **1\]** **和** ***A*** **\[** ***q*** **+1…** ***r*** **\]** **排序**

**工作量：** **子问题工作量+划分工作量**

#### **输入情况** ####

![d6c4ce33a0172e4f244244c37cdd235f.png][]

#### **工作量总和** ####

![3d37c03c562179bfc8d9c68cd7acc3f4.png][]

#### **快速排序平均工作量** ####

**假设首元素排好序在每个位置是等**

**概率的**

![ef604c63831a4d0677aae1691d5cf90e.png][]

**全部历史递推方程**

**对于高阶方程应该先化简，然后迭代**

### **差消化简** ###

**利用两个方程相减，将右边的项尽可能**

**消去，以达到降阶的目的**

![49d525e73c36f18e44a509287725af59.png][]

### **差消化简** ###

![71823da2612892ce22cb7f6b406757ad.png][]

### **迭代求解** ###

![87644981a53a35039f39dd29fea71e38.png][]

### **小结** ###

• **对于高阶递推方程先要用差消法化简为一阶方程**

• **迭代求解**

## **递归树** ##

### **有关基** **递归树的概念** **本概** ###

• **递归树是迭代计算的模型** **.**

• **递归树的生成过程与迭代过程一致** **.**

• **递归树上所有项恰好是迭代之后产**

**生和式中的项** **.**

• **对递归树上的项求和就是迭代后方**

**程的解.**

### **迭代在递归树中的表示** ###

![a75be487814c9d4496901d9178670801.png][]

### **二层子树的例子** ###

![dd61f009c7200e059efbac2f9d68bcdd.png][]

### **递归树的生成规则** ###

• **初始，递归树只有根结点** **,** **其值为** ***W*** **(** ***n*** **)**

• **不断继续下述过程：**

**将函数项叶结点的迭代式** ***W*** **(** ***m*** **)** **表示成二**

**层子树**

**用该子树替换该叶结点**

• **继续递归树的生成，直到树中无函数项**

**(只有初值)为止.**

### **递归树生成实例** ###

![0e1b3ab82e768993bdf6b9a49069cc45.png][]

![da5dde9596328848c96507525eca73bd.png][]

### **递归树** ###

![515756a6624d5ee0259bf1818b4bf918.png][]

### **对递归树上的量求和** ###

![23959af8310193180618f8629151b145.png][]

### **递归树应用实例** ###

![c16bf15529ee830b621cdba762090e88.png][]

### **求和** ###

**方程：** ***T*** **(** ***n*** **)=** ***T*** **(** ***n*** **/3)+** ***T*** **(2** ***n*** **/3)+** ***n***

**递归树层数** ***k*** **，每层** ***O*** **(** ***n*** **)**

\*\*\*\*\*\*![06a160db3d9262fda9120d3e261799f6.png][]

### **小结** ###

• **递归树是迭代的图形表述**

• **递归树的生成规则**

• **如何利用递归树求解递推方程?**

## **主定理及其证明** ##

### **主定理的应用背景** ###

**求解递推方程**

***T*** **(** ***n*** **) =** ***a T*** **(** ***n*** **/** ***b*** **) +** ***f*** **(** ***n*** **)**

***a*** **：** **归约后的子问题个数**

***n/b*** **：归约后子问题的规模**

***f*** **(** ***n*** **)** **：归约过程及组合子问题的解的**

**工作量**

**二分检索：** ***T*** **(** ***n*** **) =** ***T*** **(** ***n*** **/2)+1**

**二分归并排序：** ***T*** **(** ***n*** **) =2** ***T*** **(** ***n*** **/2)+** ***n*** **-1**

### **主定理** ###

![7cb7c7fe4d5560bfceaadbd689d1d7da.png][]

### **迭代** ###

![24c71031f162c8525fa92a21a22a1874.png][]

### **迭代结果** ###

![715d57290d64ed276c7cce22e39ccf0d.png][]

![ea71b98da12046951cd38810ea063855.png][]

![1a8325125de1bba79202e618a38a7052.png][]

![cc5fbed121c57cd4d86752a7fa97b9b3.png][]

![074bc0c059c336e25a52dc2b78df753c.png][]

![9c9d69baa6548d1ca385980114eb0a09.png][]

### **小结** ###

• **主定理的应用背景**

• **主定理的内容**

• **主定理的证明**

## **主定理的应用** ##

### **求解递推方程：例1** ###

**例** **1** **求解递推方程**

***T*** **(** ***n*** **) = 9** ***T*** **(** ***n*** **/3) +** ***n***

**解** **上述递推方程中的**

***a*** **= 9** **，** ***b*** **= 3** **，** ***f*** **(** ***n*** **) =** ***n***

***n*** **log** **3** **9** **=** ***n*** **2** **,** ***f*** **(** ***n*** **) =** ***O*** **(** ***n*** **log** **3** **9-1** **)**

**相当于主定理的** **case1** **，其中** ****** **=1.**

**根据定理得到** ***T*** **(** ***n*** **) =** ****** **(** ***n*** **2** **)**

### 求解递推放出:例2 ###

### **例** **2** **求解递推方程** ###

***T*** **(** ***n*** **) =** ***T*** **(2** ***n*** **/3) + 1**

\*\*\*\***求解递推方程：例2**

**解** **上述递推方程中的**

***a*** **= 1,** ***b*** **= 3/2,** ***f*** **(** ***n*** **) = 1** **，**

***n*** **log** **3/2** **1** **=** ***n*** **0** **= 1**

**相当于主定理的**

**Case2 .**

**根据定理得到** ***T*** **(** ***n*** **) =** ****** **( log** ***n*** **)**

![93ec6afd1a5165a4bb4b1a9cfd528c1a.png][]

### **条件验证** ###

![25ed3c59ed58cd5d9d60d411e5de9884.png][]

### **递归算法分析** ###

![2e8ae2db236bcc6a3c308559c81d0124.png][]

### **不能使用主定理的例子** ###

![c250e69e7121b2e868f299a2de12bbed.png][]

### **递归树求解** ###

![e5e170d6acf269aa916b40bf28b26987.png][]

### **求和** ###

![c8f34854ede560e428dbca2098eb89e2.png][]

### **小结** ###

• **使用主定理求解递推方程需要**

**满足什么条件？**

• **主定理怎样用于算法复杂度分**

**析？**

[954096aea6d0680ae8b9f6c3b6d9de85.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/00472833679946db9e9bc16895136384.png
[b472fab84eb04d84c595df75e7817bac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/db5d5064cfb548cbae60d0a0ad407fa8.png
[ca39918f656f434c0541419a717b264b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f37a2684f2764af5ae96a7cc6c9a34d9.png
[0d9efcb79fa29ec4cc29770be33f61d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0e5582d8757849ac9013914a3052eea8.png
[a4df46bc08dbae12932bf3e743b28334.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0553ae5879ff4329bebe34e01be8fb44.png
[8b250a7d9cd80707c0322d1b980651a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c9b9367f165144fa9eb5091464496232.png
[98f29b1b81a684efdf7d568ede2cd429.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9880c4b398bc49ef9c9e58d84bd2b2d1.png
[9d73dfa57a89b22b735710674fbcf5cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4ef5005432114bd391299cc0d7e39932.png
[b9434a4c33d8791e206867e07d07e515.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/125e3fe3585f432e8816a43c8d1cb458.png
[54bffbb92a058b9ba2d776420068fca8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a61073449ee74130860dc77283b6988d.png
[1013ca2c3ef95baf184eab4e63efc8b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ddc709a3c8134ff49f37c2a064d9d7d0.png
[0b2c8c0c1f6ed94e2e106288eec748ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ed9a459b96764b2580ba30f823fd9e45.png
[2ae850fdd922410cf6aa84a585b115f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1c40679253d74490ba96c8d431bbb776.png
[b51f27bb95a817c952ef219488282773.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b4480cfd1bdc4872b9a5e9ae15fa7ab0.png
[ce9fc4dfebe85e992d6feba880f40c8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/29a3ba43df3f44789f3aebf9d9c2f0e4.png
[8d1f977a6e0c1c43c48e6288580c21ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/a20f1c0dd9c044dc9f9501c66c152684.png
[f85ec48312ebaef80b313ddbbecac0db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/43ed16cf18804dd6b1761407aa2c7176.png
[420d2956bf3aef1a56e3aaf25accebfd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ca167a53038a4d54ba76cde83f4bb387.png
[ff03c660056545ba39ed9b3e1cc2f72a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0185ef1bd15e42318ba016a0735313ad.png
[65c857379b28cdc1b51ab347d9dafb7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/075c54ce79244c2b9a1ac6ff22ae723a.png
[3fc670e11783f6ab6d6035d4d3a8455c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/d845d7e8db104a63b6e57a78cc9de221.png
[bd0ecae654f6d2d9eb4c956487668a3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e8e1593b0f5e41dab3e52ae6717c36e7.png
[d6c4ce33a0172e4f244244c37cdd235f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/093b6b3b931b47d8b5a95b83aa58a5e1.png
[3d37c03c562179bfc8d9c68cd7acc3f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/d3457d13d26a498d844f82c05c0609ee.png
[ef604c63831a4d0677aae1691d5cf90e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/3d5091fd1a5f4de4a95f2b57481ed171.png
[49d525e73c36f18e44a509287725af59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/6fdb7bd3950c4e04982a0c379d7ba7c1.png
[71823da2612892ce22cb7f6b406757ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4150b95c7e29445abc5bd7518a925cf4.png
[87644981a53a35039f39dd29fea71e38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/35db43fbf6c64c8c9a620dfa38434fe8.png
[a75be487814c9d4496901d9178670801.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/655bf1665b5b4ef9b592d14d4de6aebc.png
[dd61f009c7200e059efbac2f9d68bcdd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/52693aac6ecb4090beadcd250eeebdb0.png
[0e1b3ab82e768993bdf6b9a49069cc45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e3117b780d914481b1ac36b3c5597999.png
[da5dde9596328848c96507525eca73bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/854819a5de7d489087cd352e59064cfc.png
[515756a6624d5ee0259bf1818b4bf918.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8af47d40102c42d294fac1b272a20c5f.png
[23959af8310193180618f8629151b145.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/da1fce4ab5b94250b3b0417d8d43001d.png
[c16bf15529ee830b621cdba762090e88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0c6c63ce2eac4050bd82e4b66f1f25d1.png
[06a160db3d9262fda9120d3e261799f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/d10f01f4b7df42ec9c9c34f9bcc38fad.png
[7cb7c7fe4d5560bfceaadbd689d1d7da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/905c28e4706f4bb99df82e962d16f212.png
[24c71031f162c8525fa92a21a22a1874.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/36357a71b6774eb48376841024ed4333.png
[715d57290d64ed276c7cce22e39ccf0d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ca03fece48f0486bb9a98ca62dbb9fca.png
[ea71b98da12046951cd38810ea063855.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4373488991354838a48b7f1770f6e6f9.png
[1a8325125de1bba79202e618a38a7052.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9f5dd41c480540dba75596a7b69a274f.png
[cc5fbed121c57cd4d86752a7fa97b9b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/97dd32389e204cc39c2f77d59da66958.png
[074bc0c059c336e25a52dc2b78df753c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ce47bdce4e6549bb87f9ef02580df3b8.png
[9c9d69baa6548d1ca385980114eb0a09.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/6c082bd55afb4f62bdd2de3426868911.png
[93ec6afd1a5165a4bb4b1a9cfd528c1a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/01143e2f24e1411b821936409f008243.png
[25ed3c59ed58cd5d9d60d411e5de9884.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f1a5f02d63e94cf0be9f5be5c064ec5f.png
[2e8ae2db236bcc6a3c308559c81d0124.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8e3b1b6fabc348ba8731efaaa3d9aa74.png
[c250e69e7121b2e868f299a2de12bbed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/99548865a2344091acdf97e602797d0f.png
[e5e170d6acf269aa916b40bf28b26987.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9996cd53493e414d92fdf962211c944a.png
[c8f34854ede560e428dbca2098eb89e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f859aaa559324c69a75c4a379cfd678b.png