算法总复习 | Panda

type

status

date

slug

summary

前置 — 算法分析

对于一般的算法时间复杂度和空间复杂度，就是找到算法中执行最多的那一行代码分析即可；

可是对于分支算法这种有递归的算法，分析起来比较困难。这里我们运用 主定理 就可以轻松分析

当规模为n的问题，可分解为a个规模为 的子问题，并且，子问题的解决需要O(f(n))，合并要O(g(n))

→→ 有:

我们分为三种情况:

👉🏼

几种常见的算法分析:

, T(1) = 1

a = 2;b = 2;k = 1 →→

⇒ —> 归并排序

a = 4;b = 2;k = 1 →→

a = 2;b = 2;k = 0 →→

⇒O(n)

贪心算法

贪婪算法分阶段工作，在每一阶段，选择局部最优解，在算法终止时，希望获得全局最优解

多处理器调度问题

给定N个作业j1,j2,…,jN，其运行时间分别是t1,t2,…,tN，处理器有多个（S），求出花费时间最短的一种方案

运行:

活动选择问题

问题描述: - 一天的时间为 0-24 - 在这期间尽可能安排多一点任务,每个时间段只能有一个活动进行

运行:

活动选择问题(加权)

我们按照权数低的优先安排的策略

运行:

饼干问题

问题描述: 分发饼干问题（Assign Cookies Problem）：假设你有一组孩子，每个孩子都有一个贪心因子（表示满足孩子所需的最小饼干大小）。同时你有一组饼干，每个饼干都有一个大小。你的目标是尽可能多地满足孩子，即尽可能多地为每个孩子分配一个满足其贪心因子的饼干。
每个孩子最多只能分配到一个饼干，每个饼干只能分配给一个孩子。
思想: 为了最大化满足的孩子数量，可以将孩子和饼干的数组都进行升序排序。然后，从最小的饼干开始，分配给贪心因子最小的孩子。这样可以有效地利用较小的饼干满足更多的孩子。

运行:

种花问题

问题描述: 种花问题（Flower Planting Problem）：假设你有一个花园花坛，花坛由一个数组表示，其中数组中的每个元素代表一个花坛的位置。数组中的值为0表示该位置没有种花，值为1表示该位置已经有一朵花。你需要在花坛中种植给定数量的花朵（n），但不允许相邻的花朵相邻种植（即两朵花不能在相邻的位置）。判断是否可以在不违反规则的情况下种植所有的花朵。
思想: 使用贪心算法，从左到右遍历花坛数组，在当前位置和其相邻位置都为空（值为0）时种植一朵花（将当前位置设为1），并递增种植的花朵数量。如果在遍历过程中，种植的花朵数量达到给定数量n，则返回True，否则在遍历结束后返回False。

写的好看点的⬇️

树上的最大独立集问题

设G=(V,E)是一个简单无向图，S是V的子集，若S中的节点在图G中都无边相连，则称S是一个独立集。(说人话就是每个节点都没有直接边相连)

对于这个问题我们采用贪心算法和动态规划来实现，我们采用dp[v][0]来表示不选择v这个节点的最大独立集个数，dp[v][1]相反之，我们对于一条边 e = (u,v)，其中u是父节点，v是孩子节点；

如果我们选择了u那么对于u的所有子节点我们都不可以选择，所以对于dp[u][1]我们就把它的所有子节点的不选择状态转移过来( sum(dp[v][0]) );

如果我们不选择u那么对于u的所有子节点它们都是没有直接边相连的，所有对于dp[u][0]我们就把u的所有子节点的最大独立集全部加起来转移给dp[u][0]

所以我们就有了以下的状态转移方程:

🫣

最后的结果就是max(dp[root][0], dp[root][1]),这就是自顶向下的树状dp

这里用C++的代码来实现

对于带权的最大独立集的大小，只要把对应的改一下转移公式就可以了

分治算法

分治算法的核心思想是把一个复杂的问题分解成为若干个的相同相似的子问题, 直到最后子问题可以简单的求解, 原问题的解就是子问题的合并 分为三步骤: → 分解（Divide） → 解决（Conquer） → 合并（combine）时间复杂度分析就用主定理！

归并排序

一直把数组从中间位置拆分成两部分,最后再通过比较,合并长度都为1的数组用主定理分析: O(NlogN)

二分查找 → 用于有序列表

对于有序数组，我们设置左右指针: - 指针指向的数大于目标就向右边求解 - 指针指向的数小于目标就向左边求解 - 直到找到目标值

最大子序列和(最大子段和)

~~这里用分治算法,本问题还可以用动态规划~~ 先把数组平均分成两组，那么最大字段就有三种情况: 1. 完全出现在中间元素的左边 → 子问题 2. 完全出现在中间元素的右边 → 子问题 3. 横跨左边和右边，也就是包含中间元素

案例: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

快速排序 - O(nlogn)

快排的基本思想就是我们每一次递归选择当前数组的中间元素，让其它比它小的元素排在这个元素的前面，比它大的元素在后面; 就是去找这个元素排完序之后应该在的位置

时间复杂度分析: T(N) = 2T(N/2) + O(N) = O(NlogN)

ಠ_ಠ最近点对问题

给定平面上有N个点,找出距离最近的两个点

动态规划

Dynamic Programing: 是一种通过将复杂问题分解为具有最优子结构和重叠子问题特性的子问题，缓存子问题的解以避免重复计算，利用空间来换取速度，从而高效求解多阶段决策过程最优化问题的方法。

最长递增子序列(Longest Increasing Subsequence)

🧐

在一个给定的整数序列中，找到一个最长的单调递增的子序列，输出其长度。

(子序列不一定要连续，但是序列中的顺序是保持不变的)

举个栗子: [10, 22, 9, 33, 21, 50, 41, 60, 80]

利用动态规划我们就要思考两个问题?

什么是状态？

状态之间如何转移？

🧐

首先我们定义dp[i]是从第i个数字结尾的最长递增子序列:

因为是最长递增的子序列, 我们确定了子序列的结尾, 我们就可以很轻松的求出在i之前的所有比a[i]小的元素, 再通过转移方程就可以求出当前的最长递增子序列

然后对于状态之间如何转移:

如果我们在第i个位置往前找, 我们要维护递增的序列, 那么要在前面的元素里面找比a[i]小的元素进行转移(因为a[i]是序列的最后一个元素), 并且要取所有dp值里面最大的来转移

⇒ dp[i] = max(dp[j] + 1 → j < i && a[j] < a[i], dp[i])

看看代码👀

最长公共子序列(Longest Common Subsequence)-LCS

问题定义🫠: 对于两个字符串A和B, 我们要找到一个可不连续的最长公共子序列, 并且输出子序列

举栗子: X = <A, B, C, B, D, A, B>; Y = <B, D, C, A, B, A>

注: 有的时候并不唯一

🧐

我们分析一下LCS的重叠子问题:

对于这个问题我们可以从这三种子问题来求解，所以这里总共有 O(mn) 个不同的子问题

🧐

我们再来分析一下LCS的递归树:

如果我们考虑所有的子问题, 那么递归树的高度可以达到O(m + n), 那么节点的个数就是个。但其实，很多子问题是相同的(比如图中的粉色区域);

⇒ 最后我们发现不同的节点数最多为 个

递推式⬇️:

🔥

看看代码👀

这种方法求LCS的时间复杂度是O(nm)

随机算法

🙃

产生随机数的方法: 线性同余法

是下一个要产生的随机数
是乘数
是增量
是模数
是当前的随机数
是随机种子

Lehmer 建议（素数），A=48271（能给出整周期）

Python 的 random 标准库中使用的随机数生成算法是梅森旋转算法（Mersenne Twister）

拉斯维加斯算法——n皇后问题

🤠

随机算法策略:

对于某行放置皇后的有效位置进行随机选取

对于某行所有列位置进行随机

回溯算法

解空间树

n皇后 → 深度为n的满n叉树 → 显约束后的解空间树是排列树

排列树

n个元素的排列树的叶子节点有 个 → 也就是有n!个排列组合

子集树

子集树的叶子结点个数:

💡

欢迎您在底部评论区留言，一起交流~