【有书共读】《算法导论》第1、2章读书笔记

第1章

第1章内容是此书的导读章节,所以在此只对一些第一次出现的必要的概念和有助于理解此书的段落进行摘抄或总结。

  • 算法:非形式地说,算法(algorithm)就是任何良定义的计算过程,该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。这样,算法就是把输入转换成输出的一个计算步骤的序列。
  • 数据结构数据结构是一种存储和组织数据的方式,旨在便于访问和修改。
  • 虽然可以把本书当做一本有关算法的“菜谱”来使用,但是也许在某一天你会遇到一个问题,一时无法很快找到一个已有的算法来解决它。所以本书将教你一些算法设计与分析的技术,以便你能自行设计算法、证明其正确性和理解其效率。
  • 本书大部分讨论有效算法。我们关于效率的一般度量是速度,即一个算法花多长时间产生结果。然而有一些问题,目前还不知道有效的解法。
  • 算法的效率很重要!
  • 使用现代计算技术,如果你对算法懂得不多,你也可以完成一些任务,但是,如果有一个好的算法背景,那么你可以做的事情就多得多。

第二章

第2章介绍了一个贯穿本书的框架,后续的算法设计与分析都是在这个框架中进行的。

  • 伪代码:用最清晰、最简洁的表示方法来说明给定的算法。

  • 循环不变式:用来证明算法的正确性。它类似于数学归纳法,其中为了证明某条性质成立,需要证明一个基本情况和一个归纳步。关于循环不变式,要证明三条性质:

    1. 初始化:循环的第一次迭代之前,它为真
    2. 如果循环的某次迭代之前它为真,那么下次迭代之前它仍未真
    3. 在循环终止时,不变时为我们提供一个有用的性质,该性质有助于证明算法是正确的
  • 算法的时间分析:对本书的大多数章节,我们假定一种通用的单处理器计算模型——随机访问及(random-access machine, RAM)来作为我们的实现技术,算法可以用计算机程序来实现。在RAM模型中,指令一条接一条地执行,没有并发操作。不考虑内存层次的影响,即不对真实情况下的高速缓存和虚拟内存进行建模。通常认为执行伪代码的一行需要常量时间,那么一个算法的运行时间可以根据数据规模(例如,待排序数组的规模n,图的顶点数和边数等)以及伪代码中每条语句的执行次数和执行时间计算出来。

    • 对于算法运行时间,我们往往集中于只求最坏运行时间

      • 最坏情况给很出了运行时间的上界。知道上界后,就能确保该算法绝不需要更长的时间。
      • 对某些算法,最坏情况经常出现。
      • “平均情况”往往与最坏情况大致一样差。
    • 增长量级:只考虑运行时间的增长率或增长量级。例如插入排序算法的最坏运行时间最终可表示为

      我们记插入排序具有最坏情况运行时间(读作“theta n 平方”)

  • 分治法:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来简历原问题的解

    分治模式在每层递归时都有三个步骤:

    • 分解原问题为若干子问题,这些子问题是原问题的规模较小的实例
    • 解决这些子问题,递归地求解各子问题。然而,若子问题的规模足够小,则直接求解
    • 合并这些子问题的解成原问题的解

    以递归排序为例:

    • 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列
    • 解决:使用归并排序递归地排序两个子序列
    • 合并:合并两个已排序的子序列以产生已排序的答案

    当待排序的序列长度为1时,递归“开始回升”,这时不需要做任何工作,因为长度为1的每个序列都已排好序

  • 分析分治算法:通常用递归方程或递归式来描述一个包含对其自身的递归调用的算法的运行时间。(第4章讲解)



#笔记##读书笔记#
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务