企业官网建设流程全解析

安康政务微平台公众号,广州网站制作实力乐云seo,怎样做网站手机客户端,电商网站建设新闻[算法设计与分析-从入门到入土] 递归 知乎#xff1a;https://www.zhihu.com/people/byzh_rc CSDN#xff1a;https://blog.csdn.net/qq_54636039 注#xff1a;本文仅对所述内容做了框架性引导#xff0c;具体细节可查询其余相关资料or源码 参考文章#xff1a;各方资…[算法设计与分析-从入门到入土] 递归知乎https://www.zhihu.com/people/byzh_rcCSDNhttps://blog.csdn.net/qq_54636039注本文仅对所述内容做了框架性引导具体细节可查询其余相关资料or源码参考文章各方资料文章目录[算法设计与分析-从入门到入土] 递归递归recursion1.归纳法Induction以选择排序求解数组 A[1...n]为例全排列生成generating permutation2.分治法divide and conquer3.动态规划dynamic programming递归recursion递归技术存在三种特殊情况归纳法Induction数学证明中的归纳思想非重叠子问题Nonoverlapping分治法(拆成p个子问题)重叠子问题overlapping动态规划(自底向上)(以空间换取时间)1.归纳法Induction核心思想:对于参数为n的问题, 先假设 “参数小于n的子问题已解决”归纳假设, 再将子问题扩展到参数为n的情况以选择排序求解数组A[1...n]为例归纳假设假设长度为n-1的子数组A[1...n-1]已能成功排序原问题转化要解决长度为n的原数组排序只需先在整个数组A[1...n]中找到最小值min将其与数组第一个元素交换位置此时原数组被拆分为“已确定有序的最小值min”和“待排序的子数组A[1...n-1]”[ m i n , A [ 1... n − 1 ] ] \big[ min, A[1...n-1] \big][min,A[1...n−1]]通过这一过程原问题的规模从n缩小到n-1最终可递推至规模为1单个元素天然有序的基准情况完成整个排序通过递推式计算比较次数C o m p a r e ( n ) { 0 n 1 ( n − 1 ) C ( n − 1 ) n ≥ 2 n ( n − 1 ) 2 \begin{align} Compare(n) \begin{cases} 0 n1 \\ (n-1) C(n-1) n \geq 2 \end{cases} \\ \frac{n(n-1)}{2} \end{align}Compare(n)​{0(n−1)C(n−1)​n1n≥2​2n(n−1)​​​全排列生成generating permutation目的: 给定整数n nn生成由数字1 , 2 , … , n 1,2,\dots,n1,2,…,n构成的所有排列归纳假设已能生成n − 1 n-1n−1个元素的所有排列原问题转化: 将第n nn个元素插入到所有可能位置从而生成n nn个元素的排列固定数字 1 在首位递归生成{ 2 , 3 , … , n } \{2,3,\dots,n\}{2,3,…,n}的所有排列固定数字 2 在首位递归生成{ 1 , 3 , … , n } \{1,3,\dots,n\}{1,3,…,n}的所有排列依次类推直到固定数字n nn在首位时间复杂度:Θ ( n ∗ n ! ) \Theta(n*n!)Θ(n∗n!)空间复杂度:Θ ( n ) \Theta(n)Θ(n)递推式写成:f ( n ) { 0 n 1 n f ( n − 1 ) n n ≥ 2 f(n) \begin{cases} 0 n1 \\ nf(n-1)n n \geq2 \end{cases}f(n){0nf(n−1)n​n1n≥2​令f ( n ) n ! h ( n ) f(n)n!h(n)f(n)n!h(n),则n ! h ( n ) n ( n − 1 ) ! h ( n − 1 ) n n!h(n)n(n-1)!h(n-1)nn!h(n)n(n−1)!h(n−1)n则h ( n ) h ( n − 1 ) 1 ( n − 1 ) ! e − 1 h(n)h(n-1)\frac{1}{(n-1)!}e-1h(n)h(n−1)(n−1)!1​e−1-f ( n ) n ! ( e − 1 ) f(n)n!(e-1)f(n)n!(e−1)e.g. 对于集合{1, 2, 3, 4}:1234,2134,3124,4123,(1234), 1324, 1423,(2134), 2314, 2413,(3124), 3214, 3412,(4123), 4213, 4312,(1234), 1243(2134), 2143(3124), 3142(4123), 4132(1324), 1342,(1423), 1432,(2314), 2341,(2413), 2431,(3214), 3241,(3412), 3421,(4213), 4231,(4312), 4321-A 4 4 24 A_4^424A44​242.分治法divide and conquer找到多数元素最小 / 最大值查找第 k 小元素查找3.动态规划dynamic programming最长公共子序列问题LCS全对最短路径问题(All-Pairs Shortest Path)0/1背包问题Knapsack