关于算法周预习作业的一些答案

第二周

  1. 适合用分治法求解的问题一般具有哪些基本特征？
    • 首先问题规模一般比较大，但是随着问题规模的缩小到一定程度便能够轻松解决
    • 各个子问题之间相互独立，无公共子问题
  2. 分治法求解问题主要包括哪几个步骤？
    • 分而治之（分解，求子问题的解，最后合并所有问题的解）
  3. 递归算法的算法框架？
    • 寻找递归方程，确定递归出口n0，若问题规模超过n0，则将问题分解成子问题
  4. 分治策略若使用递归算法实现，如何使用主定理法推算其大 O?
  5. 合并排序算法基本思想？
    • 将n个待排序的元素分成两个规模差不多的子数组，如果子数组不为单元素则继续分解。因为单元素数组默认已经排好了序，这时候再将相邻的两个数组两两合并，最后得到结果
  6. 合并排序算法解题步骤？
  7. 如何建立递归方程分析合并排序算法的时间复杂性？
    • 由T(n)=aT(n/b)+f(n)得，规模为n的问题被分为两个规模为n/2的子问题，即a=2，b=2，因此k=1。所以T(n)=O(nlogn)
  8. 二分搜索是如何完成折半查找的？
    • 有手就行
  9. 如何分析二分搜索的搜索效率？
    • 规模n的问题简化为一个规模为n/2的子问题，所以a=1，b=2，因此k=0,。所以T(n)=O(logn)

第三周

1) 二分搜索具有较高搜索效率的主要原因是什么？

  • 充分利用了元素之间的次序关系，加速了搜索进程

2) 快速排序算法包含哪几个主要步骤？

  1. 分解：一般默认第一个元素为基准元素，将数组中的元素依次与基准元素比较，比其大的放在基准右边，反之放在左边。一轮扫描结束后，基准元素应该处于整个数组的中间位置。之后以基准元素的分界点，将数组分为两段。
  2. 递归求解：若数组长度不为1，一直递归求解左右子问题
  3. 合并

3) 快速排序当选择了基准元素之后如何进行子问题划分？

  • 比基准元素小的所有元素划分为左子问题，比基准元素大的所有元素划分为右子问题

4) 为什么快速排序不需要子问题解合并的步骤？

  • 因为每次分解都对这个元素实现了排序

5) 为什么快速排序算法只有在最好情况下，时间复杂性才有 Ο(nlogn)？

  • 因为每次选择基准元素的时候，很难保证每次都选择到所有元素中的中值元素，因此也就很难均匀地划分子问题

6) 什么情况下，快速排序算法复杂性会达到 Ο(n2 )？如何改进？

  • 当每次选择的基准元素都为第一个元素，可以使用平衡快速排序和基于随机支点选择的快速排序法

7) 为什么快速排序算法只讨论平均情况下的时间复杂性？

  • 第四周

线性时间选择

  1. 线性时间选择问题提出是如何在最坏情况下用线性时间在一个包 含 n 个元素的线性序集中找到第 k 小元素。为什么采用快速排序 的 randomizedSelect 算法无法保证在最坏情况下可以用O (n )线性 时间找到第 k 小元素?
  2. 线性时间选择算法的关键是要解决划分不平衡的问题，那么如何 选择基准元素才能解决这个问题?其选择的基准元素会出现在哪 个范围之内?
  3. 线性时间选择算法基本思想的核心是什么?线性时间选择算法为 什么每一次递归搜索都至少能放弃 n/4 个元素?
  4. 如何分析线性时间选择算法的计算效率？如何由其递归方程推算 其大 O?

第六周

回溯算法框架

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜 索解空间树。其可以系统地搜索问题的所有解或任一解。

1）如何定义问题解空间？如何组织问题的解空间结构？

  • 有一个n元向量来定义解空间，通过树的形式来组织问题解空间

2）回溯法的基本思想？

  • 深度优先策略

    3）常用的问题解空间树主要包含哪两种？各自有何特点。

  • 子集树：求解的结果是集合SS的某一子集的时候

  • 排列树：求解的结果是集合SS的元素的某一种排列的时候
赏