• 计硕3班-陈陇刚-2022222278-第二章 递归与分治策略 作业

    目录

    1. 概括第二章学习内容，总结第二章学习心得

    1.1 递归

    1.1.1 递归的定义

    1.1.2 递归的使用场景

    1.2 分治

     1.2.1 分治的定义

    1.2.2 分治法使用场景

    1.3 学习心得

    2. 描述Fibonacci数列递归算法，并进行时间复杂度分析

    2.1 Fibonacci数列定义

    2.2 递归算法实现

    2.2.1 时间复杂度分析

    2.3 非递归算法实现

    2.3.2 时间复杂度分析

    3. 请设计算法，输入适当整数n，计算前n个数的全排列，对算法

    进行时间复杂度分析；简要总结算法实验心得

    3.1 核心思想

    3.2 算法实现

    3.3 结果分析

    3.4 时间复杂度分析

    4. 简要总结Karatsuba’s 大整数乘法、Strassen矩阵乘法的分治策略应用特点

    4.1 Karatsuba’s 大整数乘法的分治策略应用特点

    4.2 Strassen矩阵乘法的分治策略应用特点

    5. 证明二分搜索算法的时间复杂度为O(logn)

    6. 结合分治策略思想，讨论归并排序、快速排序的异同

    6.1 归并排序算法

    6.2 快速排序算法

    6.3 总结

    1. 概括第二章学习内容，总结第二章学习心得

    1.1 递归

    1.1.1 递归的定义

            递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用。递归的思想是把一个大型复杂问题层层转化为一个与原问题规模更小的问题，问题被拆解成子问题后，递归调用继续进行，直到子问题无需进一步递归就可以解决的地步为止。

    1.1.2 递归的使用场景

    1. 当问题和子问题具有递推关系，比如杨辉三角、计算阶乘。

    2. 具有递归性质的数据结构，比如链表、树、图。

    3. 反向性问题，比如取反。

    1.2 分治

     1.2.1 分治的定义

            分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础，例如排序算法(快速排序，归并排序)，傅里叶变换(快速傅里叶变换)等。

            分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

            分治策略：对于一个规模为n的问题，若该问题可以容易的解决(比如规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各个子问题的解合并得到原问题的解。

    1.2.2 分治法使用场景

    1. 该问题的规模缩小到一定的程度就可以容易的解决。
    2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
    3. 利用该问题分解出的子问题的解可以合并为该问题的解。
    4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

    1.3 学习心得

            递归是一种编程技巧，一种解决问题的思维方式；分治算法和动态规划很大程度上是递归思想基础上的。递归的基本思想是某个函数直接或者间接地调用自身，这样就把原问题的求解转换为许多性质相同但是规模更小的子问题。我们只需要关注如何把原问题划分成符合条件的子问题，而不需要去研究这个子问题是如何被解决的。分治法的基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些问题，然后将各个子问题的解合并成原问题的解。

    2. 描述Fibonacci数列递归算法，并进行时间复杂度分析

            斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

            在数学上，斐波纳契数列以如下递归的方法定义：

                                            F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。

    2.1 Fibonacci数列定义

    2.2 递归算法实现

    1. def Fibonnacci(n):
    2.     if (n == 0):
    3.         return 0
    4.     elif (n == 1):
    5.         return 1
    6.     return Fibonnacci(n-1) + Fibonnacci(n-2)
    7.  
    8. Fibonnacci(9)

    2.2.1 时间复杂度分析

            第n层节点个数：2^n 个
            前n层节点个数：1+2+4+……+2^n = (2 ^ n) - 1

            推理：F（n） 有 n-2层
            则F（n）一共有节点数 (2 ^ （n-2）) - 1 = ((2 ^n)/4)-1
            计算时间复杂度规则：不看常数，不看系数，只看最高次数项
            因此：O(F(n)) = O(2 ^n)

    2.3 非递归算法实现

    1. def Fibonnacci(n):
    2.     front = 0
    3.     follow = 1
    4.     result = 0
    5.     
    6.     if (n==0 or n==1):
    7.         if(n==0):
    8.             return front
    9.         return follow
    10.     while (n>=2):
    11.         n = n-1
    12.         result = front + follow
    13.         front = follow
    14.         follow = result
    15.     return result
    16.  
    17. Fibonnacci(9)

    2.3.2 时间复杂度分析

            只关注while循环里面的次数，程序从n到2即为时间复杂度O(n-2) + O(2) = O(n)。

    3. 请设计算法，输入适当整数n，计算前n个数的全排列，对算法

    进行时间复杂度分析；简要总结算法实验心得

    3.1 核心思想

            将查找一个全排列的过程看成是一棵N（N表示list的长度）叉树的深度优先遍历。当到达最大深度时候就往后退一步（相当于回溯一步）。

            每次取一个元素之后，就可以进行递归。每个元素都可以当成树的根节点。

            利用一个list来对数据进行存储。

    3.2 算法实现

    1. class FullPermutation(object):
    2.     """
    3.     无重复元素的全排列
    4.     """
    5.     def get_full_resolution(self, store, temp_list, test_list):
    6.         # 递归停止条件
    7.         # temp_list用来存储一种完整的全排列
    8.         # 如果长度已经和原始的输入test_list相等,则将这一种全排列存储下来
    9.         # 继续找下一种全排列
    10.         if len(temp_list) == len(test_list):
    11.             store.append(temp_list[:])
    12.         else:
    13.             # 遍历原始输入中的元素,每次取出一个元素
    14.             for i in test_list:
    15.                 if i in temp_list:
    16.                     continue
    17.                 # 如果当前遍历到的点不在temp_list中
    18.                 # 则添加到该列表中
    19.                 temp_list.append(i)
    20.                 # 添加完一个点之后,剩下的过程其实可以看成同样的过程
    21.                 self.get_full_resolution(store, temp_list, test_list)
    22.                 # 当找到一种全排列之后,就删掉一个点(往后退一步),继续判断其它的情况
    23.                 temp_list.pop()
    24.  
    25.     def backtrack(self, test_list):
    26.         store = []
    27.         temp_list = []
    28.         self.get_full_resolution(store, temp_list, test_list)
    29.         return store
    30.  
    31.  
    32. if __name__ == '__main__':
    33.     test_list = [1, 2, 3, 4]
    34.     c = FullPermutation()
    35.     result = c.backtrack(test_list)
    36.     for i in result:
    37.         print(i)
    38.     print('总共{}种全排列'.format(len(result)))

    3.3 结果分析

    1. [1, 2, 3, 4]
    2. [1, 2, 4, 3]
    3. [1, 3, 2, 4]
    4. [1, 3, 4, 2]
    5. [1, 4, 2, 3]
    6. [1, 4, 3, 2]
    7. [2, 1, 3, 4]
    8. [2, 1, 4, 3]
    9. [2, 3, 1, 4]
    10. [2, 3, 4, 1]
    11. [2, 4, 1, 3]
    12. [2, 4, 3, 1]
    13. [3, 1, 2, 4]
    14. [3, 1, 4, 2]
    15. [3, 2, 1, 4]
    16. [3, 2, 4, 1]
    17. [3, 4, 1, 2]
    18. [3, 4, 2, 1]
    19. [4, 1, 2, 3]
    20. [4, 1, 3, 2]
    21. [4, 2, 1, 3]
    22. [4, 2, 3, 1]
    23. [4, 3, 1, 2]
    24. [4, 3, 2, 1]
    25. 总共24种全排列

    3.4 时间复杂度分析

    1.  # 遍历原始输入中的元素,每次取出一个元素
    2.             for i in test_list:
    3.                 if i in temp_list:
    4.                     continue
    5.                 # 如果当前遍历到的点不在temp_list中
    6.                 # 则添加到该列表中
    7.                 temp_list.append(i)
    8.                 # 添加完一个点之后,剩下的过程其实可以看成同样的过程
    9.                 self.get_full_resolution(store, temp_list, test_list)
    10.                 # 当找到一种全排列之后,就删掉一个点(往后退一步),继续判断其它的情况
    11.                 temp_list.pop()

            通过观察程序段核心代码for循环语句可知，只有一重循环，且test_list 的长度为n,故时间复杂度为O(n)。 

    4. 简要总结Karatsuba’s 大整数乘法、Strassen矩阵乘法的分治策略应用特点

    4.1 Karatsuba’s 大整数乘法的分治策略应用特点

            Karatsuba乘法是一种快速乘法。用于数字比较大，相乘的结果超出了基本类型的表示范围，所以不能够直接做乘法运算的运算。此算法主要用于两个大数相乘。普通乘法的复杂度是n2，而Karatsuba算法的复杂度仅为3nlog3。

    4.2 Strassen矩阵乘法的分治策略应用特点

            Strassen算法只有在对于维数比较大的矩阵 (N>300) ，性能上才有很大的优势，可以减少很多乘法计算。Strassen算法证明了矩阵乘法存在时间复杂度低于 Θ(N3) 的算法的存在。

    5. 证明二分搜索算法的时间复杂度为O(logn)

            我们都知道二分查找在最坏的情况下依次是n/2,n/4,n/8。。。。 一直到1为止。我们假设需要循环x次才能查找到目标数，根据观察二分查找满足如下等式：

    n*(1/2)**x = 1

            经过运算得：

    2**x = n

             左右两边同时取log以2为底的对数则有：

    log2(n) = x

             去掉对数函数的底数，则可以得到二分搜索算法的实际复杂度为：

    O(log(n))

    6. 结合分治策略思想，讨论归并排序、快速排序的异同

    6.1 归并排序算法

            归并排序的核心思想其实很简单，如果要排序一个数组，我们先把数组从中间分成前后两部分，然后分别对前后两部分进行排序，再将排好序的两部分数据合并在一起就可以了。

            归并排序使用的是分治思想，分治也即是分而治之，将一个大问题分解为小的子问题来解决。分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。

            归并排序是一个稳定的排序算法，在进行子数组合并的时候，我们可以设置当元素大小相等时，先将前半部分的数据放入临时数组，这样就可以保证相等元素在排序后依然保持原来的顺序。

            不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递归公式。

            如果我们对 n 个元素进行归并排序所需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)，而合并两个子数组的时间复杂度为 O(n)。所以，归并排序的时间复杂度计算公式为:

                                                             T(1)=C

                                                            T(n)=2∗T(n2)+n,n>1

     

    用大 O 标记法来表示，归并排序的时间复杂度为 O(nlogn)。

            从我们的分析可以看出，归并排序的执行效率与原始数据的有序程度无关，其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。

            归并排序有一个缺点，那就是它不是原地排序算法。在进行子数组合并的时候，我们需要临时申请一个数组来暂时存放排好序的数据。因为这个临时空间是可以重复利用的，因此归并排序的空间复杂度为 O(n)，最多需要存放 n 个数据。

    6.2 快速排序算法

            快速排序的思想是，如果要对数组区间 [p, r] 的数据进行排序，我们先选择其中任意一个数据作为 pivot（分支点），一般为区间最后一个元素。然后遍历数组，将小于 pivot 的数据放到左边，将大于 pivot 的数据放到右边。接着，我们再递归对左右两边的数据进行排序，直到区间缩小为 1 ，说明所有的数据都排好了序。

            归并排序是由下向上的，先处理子数组然后再合并。而快速排序正好相反，它的过程是由上向下的，先分出两个子区间，再对子区间进行排序。归并排序是稳定的时间复杂度为 O(n)，但它是非原地算法，而快排则是原地排序算法。

            如果快速排序每次都将数据分成相等的两部分，则快排的时间复杂度和归并排序相同，也是 O(nlogn)，但这种情况是很难实现的。如果数据原来已经是有序的，则每次的分区都是不均等的，我们需要进行 n 次分区才能完成整个排序，此时快排的时间复杂度就退化成了 O(n2)。

            平均时间复杂度的求解也可以通过递归树来分析，这个问题留待我们以后再解决。我们现在只需要知道，在大部分情况下，快速排序的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化成 O(n2)。

            快速排序是一个原地排序算法，是一个不稳定的排序算法，因为其在数据交换过程中可能会改变相等元素的原始位置。

    6.3 总结

            归并排序和快速排序都是利用分治的思想，代码都通过递归来实现，过程非常相似。

            归并排序非常稳定，时间复杂度始终都是 O(nlogn)，但不是原地排序；快速排序虽然最坏情况下时间复杂度为 O(n2)，但平均情况下时间复杂度为 O(nlogn)，最坏情况发生的概率也比较小，而且是原地排序算法，因此应用得更加广泛。

  • 相关阅读:
    【Kubernetes | Pod 系列】Pod 的基本管理（1）——对 Pod 的创建
    使用本地自签名证书为 React 项目启用 https 支持
    技术栈选型的时候，ruby、go、java、vue、react应该怎么选择？
    Self-Polish: Enhance Reasoning in Large Language Models via Problem Refinement
    Databend使用入门
    【CNN-FPGA开源项目解析】卷积层01--floatMult16模块
    8.菜品展示、购物车、下单开发
    java考点之程序看界面响应
    ES6 class 类
    2022完整版：云计算面试题和答案（学习复习资料）
  • 原文地址：https://blog.csdn.net/GUIDchen/article/details/128018508