算法设计与分析笔记

定义

算法应该具有5个特性:有穷性,确定性,可行性,0个或多个数据输入,一个或多个数据输出

算法的复杂性分为时间复杂性(主要判断算法是否优秀的依据)、空间复杂性

Ο,读音:big-oh;表示上界,小于等于

Ω,读音:big omega、欧米伽;表示下界,大于等于

Θ,读音:theta、西塔;既是上界也是下界,称为确界,等于

ο,读音:small-oh;表示上界,小于

ω,读音:small omega;表示下界,大于

问题和问题求解

    问题求解:寻找一种方法来实现目标。

    问题求解过程:人们通过使用问题领域知识来理解和定义问题,并凭借自身的经验和知识求选择和使用适当的问题求解策略、技术和工具,将一个问题描述转换成问题解的过程。

    计算机求解问题的关键之一是寻找一种问题求解策略得到求解问题的算法,从而得到问题的解。

问题求解过程

  1. 理解问题

  2. 设计方案

  3. 实现方案

  4. 回顾复查

  1. 理解问题

  2. 选择数据结构、精确解/近似解

  3. 设计算法

  4. 证明正确性(确定性,有穷性)

  5. 分析算法

  6. 设计程序

算法的复杂度

一个好的算法应具备以下4个重要特性:

最常见的多项式时间算法的渐近时间复杂度

    O(1)<O(log n)<O(n)<O(nlog n)<O(n2)<O(n3)

最常见的指数时间算法的渐近时间复杂度

     O(2n)<O(n!)<O(nn)

算法的分析

算法的分析主要分为两种:①递归算法的分析②非递归算法的分析

递归

递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决

递归的三要素

在我们了解了递归的基本思想及其数学模型之后,我们如何才能写出一个漂亮的递归程序呢?笔者认为主要是把握好如下三个方面:

1). 明确递归终止条件

我们知道,递归就是有去有回,既然这样,那么必然应该有一个明确的临界点,程序一旦到达了这个临界点,就不用继续往下递去而是开始实实在在的归来。换句话说,该临界点就是一种简单情境,可以防止无限递归。

2). 给出递归终止时的处理办法

我们刚刚说到,在递归的临界点存在一种简单情境,在这种简单情境下,我们应该直接给出问题的解决方案。一般地,在这种情境下,问题的解决方案是直观的、容易的。

3). 提取重复的逻辑,缩小问题规模*

我们在阐述递归思想内涵时谈到,递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题,这些子问题可以用相同的解题思路来解决。从程序实现的角度而言,我们需要抽象出一个干净利落的重复的逻辑,以便使用相同的方式解决子问题。

递归算法的分析

我们大致分为两种方法,第一种是主定理方法解递归方程,第二种就是递归树,其中递归树是最常用,最易懂的方法!关于递归树,这个文章就非常不错

主定理

先搬出我们的主定理吧.

我不想思考主从定理为什么这么快,为什么正确,为什么这样写...

分治算法

适合分支策略的算法是:问题可以被拆分成多个子问题,且子问题之间相互独立并与原问题相同

回溯算法

回溯是一种即具有系统性又具有跳跃性的搜索算法,有”通用解题法“之称。

四皇后问题

四皇后问题是一张四乘四的棋盘,在棋盘中放四颗棋子,要求如下:任意两个皇后都不能处在同一行、同一列 任意两个皇后都不能处在同一斜线上(主斜线、反斜线)。

四皇后是八皇后的衍生版本,其原理都是一样的。八皇后说的是在8×8的国际棋盘上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法?八皇后一共有92种解法。而四皇后是在一个4×4的棋盘上摆放4个皇后。

动态规划

问题必须具有:①最优子结构 ②重叠的子问题

解题步骤是:

  1. 找出最优解的性质,刻画最优解的结构

  2. 递归定义最优值

  3. 自底向上的方式计算最优值

  4. 根据最优值构造最优解