算法分析与设计复习

算法分析与设计复习

2016年初,研一上学期期末考试前,复习并总结算法分析与设计科目的内容。复习过程参照《算法导论》中文第2版,同时参照PPT,章节划分根据PPT内容



概要:

第一章 概述

第二章 插入排序&分治策略

第三章 复杂度分析

第四章 堆与堆排序

第五章 快速排序

第六章 线性时间排序


第一章 概述

  1. 算法的应用范围

    算法在诸如生物等诸多领域有其应用

  2. 算法的意义

    算法在很多情况下让不可能完成的事情变成了可能,让处理的很慢的过程变快。

  3. 一个铺垫

    一串不全为0的数,怎么取能拿到一段和最大的子串

第二章 插入排序&分治策略

  1. 插入排序

    • 掌握插入排序的方法
    • 循环不变式的证明(不考)

      初始化:

      保持:

      终止:

    • 逐步计算插入排序的时间复杂度:

      结论(基于RAM模型下):

      Best Case:O(n)

      Worst Case:O(n^2)

  2. 分治策略
    • 概述:

      大问题拆成多个小问题,分别计算每个小问题的解最后把多个小问题合成原问题的解

  3. MERGE Sort
    • 掌握归并排序的方法
    • 分析归并排序
      • Best case:nlgn
      • Worst case:nlgn
  4. 课后习题总结
    • 推演一个插入排序的过程
    • 循环不变式证明线性查找的正确性
    • 对给定的时间复杂度表达式写出Θ
    • 推演一个MERGE Sort
    • 算法设计题:可以看*

第三章 复杂度分析

  1. 时间复杂度分析

    • O(n)1上界

      • o不精确的上界
    • Ω(n)2下界
      • ω不精确的下界
    • θ(n)3精确界
  2. 归并排序分析
    • 代换法

      • 做一个好的猜测
      • 假设这个界对某一个范围内成立
      • 带入得出结论
      • 数学归纳法证明结论正确
    • 递归树
      • 时间复杂度的表达式是每一层拆分开销之和加上最底层每一个未知的开销。
    • 主定理
      • 形如:T(n)=aT(n/b)+f(n)
      • 三种情况:
        • 若存在ε>0,有f(n)=O(n^(log b(a)-ε)),则T(n)=Θ(n^(log b(a)))
        • 若f(n)=Θ(n^(log b(a))),T(n)=Θ(n^(log b(a))lg(n))
        • 若对某ε>0,有f(n)=Ω(n^(log b(a)+ ε)),且对常数c<1与所有足够大的n,有af(n/b)<=cf(n),则T(n)=Θ(f(n))
  3. 课后习题总结
    • 代换法证明时间复杂度

      • 猜测渐进确界,证明之
      • 主方法可用情况的练习
      • 判断主方法是否可用,确定渐进上界

第四章 堆与堆排序

  1. 堆的概念

    • 利用树的数组存储方式,PARENT(i) = ?, LEFT(i) = 2i, RIGHT(i) = 2i + 1
  2. 两个关键的函数
    • MAX-HEAPIFY 已有堆的情况下,加入新结点后调整堆以使得其满足堆的条件。O(lgn)
    • BUILD-MAX-HEAP 基于无序数组调整为大顶堆Θ(n)
    • 其中,BUILD-MAX-HEAP是由(n/2)向下取整次MAX-HEAPIFY组成的,但其时间复杂度是Θ(n)
  3. 堆排序时间复杂度
    • 时间复杂度由两部分组成,1次BUILD-MAX-HEAP,n-1次MAX-HEAPIFY,故结果为T(n)=Θ(n)+nO(lg n)=O(nlgn)
    • 最好的情况下,时间复杂度为O(n)
  4. 优先级队列
  5. 必会技能:
    • 区分一个数组是不是堆
    • 手工跑堆排序或者建堆过程
  6. 课后习题总结:
    • 区分一个序列是否为最大堆
    • 画出一个完整的MAX-HEAPIFY流程

第五章 快速排序

  1. 快速排序

    • 时间复杂度

      • 最好Θ(nlgn)
      • 平均Θ(nlgn)
      • 最坏Θ(n2)
    • 知道分治的过程————以一个数做分治,分成两组
    • 掌握快排的手动做法
    • 有一个关于每次都从1/10位置分隔的情况下仍为nlgn的证明
  2. 随机快排
    • 关键:用随机来避免出现Worst case
    • 实际表现是最快的排序
    • 时间复杂度
      • 平均Θ(nlgn)
      • 最坏Θ(n2) (仅在理论上存在)
  3. 课后习题总结
    • 若快排数组中元素都一样,时间复杂度是多少?
    • 答:这是Worst Case 所以是Θ(n2)

第六章 线性时间排序

  1. BDD证明比较类排序最坏情况的下界是nlgn
  2. 计数排序
    • 计数排序是一种稳定排序
    • 时间复杂度Θ(k+n) ,在k与n同一数量级时,该复杂度为O(n)
    • 关键:被排序的n个数在0~k之间
      • 若这n个数的范围是n^2,则时间复杂度不再是O(n),而是O(n^2)
    • 掌握计数排序的完整过程,可以手跑
      1. 创建一个容量为k的数组C,并将所有元素置零
      2. 遍历原数组A,在C中对应的位置+1
      3. 遍历数组C,从第2个元素开始的所有元素的值依次用前一个元素与当前元素的和替换。
      4. 逆序遍历A,拿到元素a,在C中查找其位置(即C中元素对应的数值)在数组B中的对应位置放入a即可。同时将C中的那个数据-1
  3. 基数排序
    • 掌握基数排序的完整过程,可以手跑
    • 基数排序的特点:利用稳定排序的特点,从低位到高位按位排序
    • 时间复杂度
      • Θ(d T(n))
      • 在每位计算使用计数排序的时候,时间复杂度为Θ(n)
  4. 桶排序
    • 掌握桶排序的完整过程,可以手跑
    • 要点:类似于计数排序,为待排序数组提供若干个区间,将各个待排序的数放进区间内,完成区间内排序的同时,就得到了一个完整的排序结果。
  5. 算法小结(重要考点)

  1. 助记:O,my god——上帝、上界 ??
  2. 助记:欧米伽——家在地上,下界 ??
  3. 助记:θ的中间的一横足以说明是中间的啊~ ??
时间: 01-08

算法分析与设计复习的相关文章

系统分析与设计复习总结之【领域模型】

五一三天假除了背单词,也抽空复习了下UML,毕竟还有一两周要半期考试了--(哪里来的半期考试啊syllabus明明里提都没有提啊T_T)今天先来看--领域模型. 首先领域模型长这样(后面还有九个图啊千万不要搞混了) 那么为什么要有领域模型呢,不是前面已经有用例图了嘛.书上在后面的内容稍微提到了这点,表示领域模型可以减小人们的思维与软件模型之间的表示差异.我自己在在其他资料上看到了另外一种更通俗的解释,大概是这么说的,因为用例是用纯自然语言写的,是没有"类"的概念的,无法从自然语言转换到

Java算法分析与设计视频教程下载

下载地址:http://pan.baidu.com/s/1i4pMZ9z 密码:v9ra 算法分析与设计Java版,是一套实用型算法课程.通过本课程的学习,学员可以掌握以下技术点:线性结构与顺序表.单向链表.循环链表.栈的基本概念.链式堆栈.中缀表达式.队列.链式队列.串.MyString.Brute-Force算法.MySet类实现.矩阵类.递归算法.哈夫曼树.希尔排序.HashTable算法等内容. 第一讲.算法基本概述.抽象数据类型 第二讲.算法的设计目标.时间复杂度和空间复杂度 第三讲.

Java实战应用视频教程之Java算法分析与设计

实战应用Java算法分析与设计(链表.二叉树.哈夫曼树.图.动态规划.HashTable算法)适合人群:中级课时数量:38课时用到技术:Java算法涉及项目:案例应用实战咨询qq:1840215592课程简介:算法分析与设计Java版,是一套实用型算法课程.通过本课程的学习,学员可以掌握以下技术点:线性结构与顺序表.单向链表.循环链表.栈的基本概念.链式堆栈.中缀表达式.队列.链式队列.串.MyString.Brute-Force算法.MySet类实现.矩阵类.递归算法.哈夫曼树.希尔排序.Ha

算法分析与设计——贪心法实验报告

   算法导论  课程设计 成 绩 题    目:    贪心法 学院班级:        1613013         学    号:      16130130216       姓    名:        库 妍           主讲教师:        张立勇          日    期:       2019.5.9         一.Knapsack Problem 1.实验题目 下面有5个具有值和权重列表的项目,背包最多可以包含100磅.解决了分数背包和0/1背包问题

算法分析与设计——分治法实验报告

   算法导论  课程设计 成 绩 题    目:  算法导论课程设计实验报告 学院班级:        1613013         学    号:      16130130216       姓    名:        库 妍           主讲教师:        张立勇          日    期:       2019.6.3         录 分治法 一.Implement exercise 2.3-7................................

算法分析与设计——动态规划法实验报告

   算法导论  课程设计 成 绩 题    目:    动态规划法 学院班级:        1613013         学    号:      16130130216       姓    名:        库 妍           主讲教师:        张立勇          日    期:       2019.4.11         (1)描述最优子结构:如果最优的加括号的方式将其分解为Ai..k与Ak+1..j的乘积,则分别对Ai..k与Ak+1..j加括号的方式也

南邮算法分析与设计实验2 动态规划法

动态规划法 实验目的: 加深对动态规划法的算法原理及实现过程的理解,学习用动态规划法解决实际应用中的最长公共子序列问题. 实验内容: 用动态规划法实现求两序列的最长公共子序列,其比较结果可用于基因比较.文章比较等多个领域. 实验要求: 掌握动态规划法的思想,及动态规划法在实际中的应用:分析最长公共子序列的问题特征,选择算法策略并设计具体算法,编程实现两输入序列的比较,并输出它们的最长公共子序列. 实验原理及内容(包括操作过程.结果分析等) 1.最长公共子序列(LCS)问题是:给定两个字符序列X=

南邮算法分析与设计实验3 回溯法

回溯法 实验目的: 学习编程实现深度优先搜索状态空间树求解实际问题的方法,着重体会求解第一个可行解和求解所有可行解之间的差别.加深理解回溯法通过搜索状态空间树.同时用约束函数剪去不含答案状态子树的算法思想,会用蒙特卡罗方法估计算法实际生成的状态空间树的结点数. 实验内容: 1.求24点问题 给定四个1-9之间的自然数,其中每个数字只能使用一次,用算术运算符+,-,*,/构造出一个表达式,将这4个正整数连接起来(可以使用括号),使最终的得数为24.要求根据问题的特征设计具体算法并编程实现,输入数据

南邮算法分析与设计实验4 密码算法

实验目的 了解现代密码学的基本原理和数论的基础知识,掌握非对称密码体制的著名代表RSA加密算法的工作原理和流程,并设计实现一个简单的密钥系统. 实验内容 了解加/解密的基本原理和工作过程,用公开密钥对明文进行加密,并用私人密钥对密文进行解密,构造一个简单的 RSA 公开密钥系统. 实验原理 1.RSA算法是由麻省理工学院的 Ron Rivest,Adi Shamir 和Len Adleman 于 1977 年研制并于1978 年首次发表的一种算法,是第一个能同时用于加密和数字签名的算法,且易于理