简介

  • 算法导论 阅读笔记

第一章 算法在计算中的作用

算法

  • 非形式地说，算法(algorithm)就是任何良定义的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。这样算法就是把输入转换成输出的计算步骤的一个序列。

  • 一般来说，问题实例由计算该问题解所必须的(满足问题陈述中强加的各种约束的)输入组成。

  • 因为许多程序使用排序作为一个中间步，所以排序是计算机科学中的一个基本操作。

第二章 算法基础

插入排序

  • 插入排序，对于少量元素的排序，它是一个有效的算法

分治法

  • 许多有用的算法在结构上是递归的：
    • 为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。
  • 这些算法典型的遵循分治法的思想：
    • 将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
  • 分治模式在每层递归时都有三个步骤：
    • 分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
    • 解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。
    • 合并这些子问题的解成原问题的解
  • 归并排序算法完全遵循分治模式。直观上其操作如下：
    • 分解：分解待排序的N个元素的序列成各觉有N/2个元素的两个子序列。
    • 解决：使用归并排序递归地排序两个子序列
    • 合并：合并两个已经排序的子序列以产生已排序的答案。

分析分治算法

  • 当一个算法包含对其自身的递归调用时，我们往往可以用递归方程或递归式来描述其运行时间，该方程根据在较小输入上的运行时间来描述在规模为n的问题上的总运行时间。然后，我们可以使用数学工具来求解该递归式并给出算法性能的界

第三章 函数的增长

渐近记号

  • 我们将主要使用渐近记号来描述算法的运行时间

第四章 分治策略

  • 归并排序利用了分支策略。在分支策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤：
    • 分解(Divide)步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
    • 解决(Conquer)步骤递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解。
    • 合并(Combine)步骤将子问题的解组合成原问题的解
  • 当子问题足够大，需要递归求解时，我们称之为递归情况(recursive case).

  • 当子问题变得足够小，不再需要递归时，我们说递归已经“触底”，进入了基本情况(base case)。有时，除了与原问题形式完全一样的规模更小的子问题外，还需要求解与原问题不完全一样的子问题。我们将这些子问题的求解看做合并步骤的一部分。

  • 递归式
    • 递归式与分支方法是紧密相关的。因为使用递归式可以很自然地刻画分支算法的运行时间。
    • 一个递归式(recurrence)就是一个等式或不等式，他通过更小的输入上的函数值来描述一个函数。

第五章 概率分析和随机算法

概率分析

  • 概率分析是在问题分析中应用概率的理念。

  • 更一般的，如果一个算法的行为不仅由输入决定，而且也由随机数生成器(random-number generator)产生的数值决定，则称这个算法是随机的(randomized)