热搜关键词: 信号与系统无刷电机ADSTCP/IP

pdf

算法详解 卷1 算法基础

  • 1星
  • 日期: 2022-04-03
  • 大小: 7.02MB
  • 所需积分:1分
  • 下载次数:5
  • favicon收藏
  • rep举报
  • free评论
标签: 算法

算法

算法是计算机科学领域*重要的基石之一。算法是程序的灵魂,只有掌握了算法,才能轻松地驾驭程序开发。  算法详解系列图书共有4卷,本书是第1卷——算法基础。本书共有6章,主要介绍了4个主题,它们分别是渐进性分析和大O表示法、分治算法和主方法、随机化算法以及排序和选择。附录A和附录B简单介绍了数据归纳法和离散概率的相关知识。本书的每一章均有小测验、章末习题和编程题,这为读者的自我检查以及进一步学习提供了较多的便利。  本书为对算法感兴趣的广大读者提供了丰富而实用的资料,能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生,想要培养和训练算法思维和计算思维的IT专业人士,以及在准备面试的应聘者和面试官阅读参考。

第  1章  绪论  1

1.1  为什么要学习算法  1

1.2  整数乘法  3

1.2.1  问题和解决方案  3

1.2.2  整数乘法问题  3

1.2.3  小学算法  4

1.2.4  操作数量的分析  5

1.2.5  还能做得更好吗  5

1.3  Karatsuba乘法  6

1.3.1  一个具体的例子  6

1.3.2  一种递归算法  7

1.3.3  Karatsuba乘法  9

1.4  MergeSort算法  11

1.4.1  推动力  11

1.4.2  排序  12

1.4.3  一个例子  13

1.4.4  伪码  14

1.4.5  Merge子程序  15

1.5  MergeSort算法分析  16

1.5.1  Merge的运行时间  17

1.5.2  MergeSort的运行时间  18

1.5.3  定理1.2的证明  19

1.5.4  小测验1.1~1.2的答案  23

1.6  算法分析的指导原则  23

1.6.1  第  1个原则:坏情况分析  24

1.6.2  第  2个原则:全局分析  25

1.6.3  第3个原则:渐进性分析  26

1.6.4  什么是“快速”算法  27

1.7  本章要点  28

1.8  习题  29

挑战题  31

编程题  31

第  2章  渐进性表示法  32

2.1  要旨  32

2.1.1  推动力  32

2.1.2  高级思维  33

2.1.3  4个例子  34

2.1.4  小测验2.1~2.4的答案  38

2.2  大O表示法  40

2.2.1  文本定义  40

2.2.2  图形定义  40

2.2.3  数学定义  41

2.3  两个基本例子  42

2.3.1  k阶多项式是O(nk)  42

2.3.2  k阶多项式不是O(nk-1)  43

2.4  大Ω和大  表示法  44

2.4.1  大Ω表示法  44

2.4.2  大  表示法  45

2.4.3  小O表示法  46

2.4.4  渐进性表示法的来源  47

2.4.5  小测验2.5的答案  48

2.5  其他例子  48

2.5.1  在指数中添加一个常数  48

2.5.2  指数乘以一个常数  49

2.5.3  值vs.和  49

2.6  本章要点  50

2.7  习题  51

第3章  分治算法  53

3.1  分治法规范  53

3.2  以O(n  log  n)时间计数逆序对  54

3.2.1  问题  54

3.2.2  一个例子  54

3.2.3  协同筛选  55

3.2.4  穷举搜索法  55

3.2.5  分治法  56

3.2.6  高级算法  57

3.2.7  关键思路:站在MergeSort的肩膀上  57

3.2.8  重温Merge  58

3.2.9  Merge和分离逆序对  60

3.2.10  Merge_and_CountSplitInv  61

3.2.11  正确性  61

3.2.12  运行时间  62

3.2.13  小测验3.1~3.2的答案  62

3.3  Strassen的矩阵相乘算法  63

3.3.1  矩阵相乘  63

3.3.2  例子(n  =  2)  64

3.3.3  简单算法  64

3.3.4  分治法  65

3.3.5  节省一个递归调用  67

3.3.6  细节  68

3.3.7  小测验3.3的答案  69

*3.4  O(n  log  n)时间的近点对(Closest  Pair)算法  70

3.4.1  问题  70

3.4.2  热身:1D情况  71

3.4.3  预处理  71

3.4.4  一种分治方法  72

3.4.5  一个微妙的变化  74

3.4.6  ClosestSplitPair  74

3.4.7  正确性  76

3.4.8  辅助结论3.3(a)的证明  77

3.4.9  辅助结论3.3(b)的证明  78

3.4.10  小测验3.4的答案  80

3.5  本章要点  80

3.6  习题  81

挑战题  81

编程题  82

第4章  主方法  83

4.1  重温整数乘法  83

4.1.1  RecIntMult算法  84

4.1.2  Karatsuba算法  84

4.1.3  比较递归过程  85

4.2  形式声明  86

4.2.1  标准递归过程  86

4.2.2  主方法的陈述和讨论  87

4.3  6个例子  88

4.3.1  重温MergeSort  89

4.3.2  二分搜索  89

4.3.3  整数乘法的递归算法  90

4.3.4  Karatsuba乘法  90

4.3.5  矩阵乘法  91

4.3.6  一个虚构的递归过程  92

4.3.7  小测验4.2~4.3的答案  93

*4.4  主方法的证明  94

4.4.1  前言  94

4.4.2  重温递归树  95

4.4.3  单层所完成的工作  96

4.4.4  各层累计  97

4.4.5  正义与邪恶:需要考虑3种情况  98

4.4.6  预告运行时间上界  99

4.4.7  后的计算:第  一种情况  100

4.4.8  迂回之旅:几何级数  101

4.4.9  后的计算:第二种情况和第三种情况  102

4.4.10  小测验4.4~4.5的答案  103

4.5  本章要点  103

4.6  习题  104

第5章  快速排序(QuickSort)  107

5.1  概述  107

5.1.1  排序  108

5.1.2  根据基准元素进行划分  108

5.1.3  高级描述  110

5.1.4  内容前瞻  110

5.2  围绕基准元素进行划分  111

5.2.1  简易方法  111

5.2.2  原地实现:高级计划  112

5.2.3  例子  113

5.2.4  Partition子程序的伪码  115

5.2.5  QuickSort的伪码  117

5.3  良好的基准元素的重要性  117

5.3.1  ChoosePivot的简单实现  118

5.3.2  ChoosePivot的过度实现  118

5.3.3  小测验5.1~5.2的答案  119

5.4  随机化的QuickSort  121

5.4.1  ChoosePivot的随机化实现  121

5.4.2  随机化QuickSort的运行时间  122

5.4.3  直觉:随机基准元素为什么很好  123

*5.5  随机化QuickSort的分析  124

5.5.1  预备工作  125

5.5.2  分解蓝图  126

5.5.3  应用蓝图  128

5.5.4  计算比较的概率  130

5.5.5  后的计算  132

5.5.6  小测验5.3的答案  133

*5.6  排序需要  (n  log  n)的比较  134

5.6.1  基于比较的排序算法  134

5.6.2  具有更强前提的更快速排序  135

5.6.3  定理5.5的证明  136

5.7  本章要点  138

5.8  习题  139

挑战题  140

编程题  141

第6章  线性时间级的选择  142

6.1  RSelect算法  143

6.1.1  选择问题  143

6.1.2  简化为排序  144

6.1.3  分治法  145

6.1.4  RSelect的伪码  146

6.1.5  RSelect的运行时间  147

6.1.6  小测验6.1~6.2的答案  149

*6.2  RSelect的分析  150

6.2.1  根据阶段追踪进展  150

6.2.2  简化为掷硬币  151

6.2.3  综合结论  153

*6.3  DSelect算法  154

6.3.1  基本思路:中位的中位元素  154

6.3.2  DSelect的伪码  155

6.3.3  理解DSelect  156

6.3.4  DSelect的运行时间  157

*6.4  DSelect的分析  159

6.4.1  递归调用之外所完成的工作  159

6.4.2  一个粗略的递归过程  159

6.4.3  30-70辅助结论  160

6.4.4  解析递归过程  163

6.4.5  先猜后验方法  164

6.5  本章要点  166

6.6  本章习题  166

挑战题  167

编程题  168

附录A  快速回顾数学归纳法  169

附录B  快速回顾离散概率  173

推荐帖子 最新更新时间:2022-05-16 23:53

【晒样片】+TI芯片申请小体会
     TI是非常大方的一个公司,对于学生党来说,芯片性能很高,足以应付各种比赛和日常的一些小的项目。      首先,个人认为TI样片申请主要是两个目的,第一个是对芯片性能进行测试,看用户体验,虽然对于公司来说,这个不会有太大意义。其次,就是芯片推广,每当有新的芯片面相市场时,高昂的价格肯定会把很大一部分消费者挡在门外,只有了解芯片性能才能够大规模去采购。      然后那,根据自身经验,
Mr.shan TI技术论坛
【直播】恩智浦Thread/BLE双模技术讲座,预报名有礼
直播时间:8月25日9:30(提前半小时在活动页面开放直播通道,第一位入场者有小礼品哦) 点此进入活动页面,报名看直播  本次直播嘉宾由恩智浦的市场和资深技术人员组成,市场人员为大家讲述恩智浦微控制器业务内容、恩智浦无线MCU产品及方案介绍,资深技术人员为大家讲解Thread和BLE双模开发内容。 直播干货看点1 恩智浦资深技术工程师结合KW41大赛网友遇到的开发难点,详解KW41的Thr
EEWORLD社区 NXP MCU
【TI首届低功耗设计大赛】MSP430FR5969学习之CCS工程建立
CCS新建工程和IAR差不多,无非就是芯片选型,路径啊这些的。 不知道Identify是不是选择芯片型号用的,点了下试试。弹出这么个对话框。 然后居然弹出通信失败,不知道啥原因。可能是RTS和CTS没有接上吧,知道的朋友告诉我下哈。谢谢~ 新建工程就是如下所示了。咱们的芯片是MSP430FR5969 第一次编译会弹出这个对话框,至于干啥用的,好像是低功耗选项的管理。暂时用不
lonerzf 微控制器 MCU
MSP430 需配合何种晶振工作?
被用于MSP430 的32.768KHz 的晶振应具有如下重要的规格:负载电容(在数据手册中有明确说明)注:有效负载电容晶振制造商通常在晶振的数据手册中明确指出晶振的有效负载电容。电容应串行地连接在XIN 和XOUT 的引脚上,这样,有效负载电容应是:C(eff) = {C(XIN)   C(XOUT)}/{C(XIN) + C(XOUT)}因此,晶振的数据手册中所指出的12pF 的有效负载电容即
莫妮卡 微控制器 MCU
【Altera SoC体验之旅】安装多个版本Quartus II带来的问题
申请了一块SoCkit板子试用,所以需要更新电脑里的Quartus II,由于本身项目中必须使用ArriaGX器件,所以之前的Quartus II12.1也不能卸载,固电脑中存在两个版本,分别是Quartus II12.1与Quartus II14.1.今天在跑例程的时候,使用随板附带的批处理下载配置文件的时候出现了一个问题,该批处理的内容如下:%QUARTUS_ROOTDIR%\\bin\\qu
coyoo Altera SoC
SAR ADC 的输入注意事项
输入信号可能会影响为应用选择最佳逐次逼近寄存器 (SAR) 模数转换器 (ADC) 的方式? 在我们听到“输入”两个字时,脑海里会立即浮现频率、幅值、正弦波以及锯齿波等几件事。所有这些都是优化信号调节时需要考虑的相关问题。 但是,很多人不会预先考虑的一件事是 SAR ADC 的实际输入类型。在本博客中,我将重点介绍三种 SAR 输入(单端、伪差分与差分输入)以及如何将其使用在应用中。在以后的博
fish001 模拟与混合信号

评论

登录/注册

意见反馈

求资源

回顶部

热门活动

相关视频

可能感兴趣器件

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版 版权声明

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京B2-20211791 京ICP备10001474号-1 电信业务审批[2006]字第258号函 京公网安备 11010802033920号 Copyright © 2005-2022 EEWORLD.com.cn, Inc. All rights reserved
×