🗒️算法设计与分析
00 分钟
2024-4-21
2024-11-7
type
status
date
slug
summary
tags
category
icon
password

一、搜索

1、遍历搜索

2、二分查找

二分查找（binary search）是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。
时间复杂度为 𝑂(log⁡𝑛) ：在二分循环中，区间每轮缩小一半，因此循环次数为 log2⁡𝑛 。
空间复杂度为 𝑂(1) ：指针 𝑖 和 𝑗 使用常数大小空间。
优缺点
  • 二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。因为排序算法的时间复杂度通常为𝑂(𝑛log⁡𝑛)，比线性查找和二分查找都更高。对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为𝑂(𝑛)，也是非常昂贵的。
  • 二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素，而在链表中执行跳跃式访问的效率较低，因此不适合应用在链表或基于链表实现的数据结构。
  • 小数据量下，线性查找性能更佳。在线性查找中，每轮只需 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量  较小时，线性查找反而比二分查找更快。
 

二、排序

1、选择排序

选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。
设数组的长度为 𝑛 。
  1. 初始状态下，所有元素未排序，即未排序（索引）区间为 [0,𝑛−1] 。
  1. 选取区间 [0,𝑛−1] 中的最小元素，将其与索引 0 处的元素交换。完成后，数组前 1 个元素已排序。
  1. 选取区间 [1,𝑛−1] 中的最小元素，将其与索引 1 处的元素交换。完成后，数组前 2 个元素已排序。
  1. 以此类推。经过 𝑛−1 轮选择与交换后，数组前 𝑛−1 个元素已排序。
  1. 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。
  • 时间复杂度为 𝑂(𝑛2)：外循环共 n-1 轮，第一轮的未排序区间长度为 n ，最后一轮的未排序区间长度为2，即各轮外循环分别包含n、n-1···3、2轮内循环，求和为 (n-1)(n+2)/2 。
  • 空间复杂度为 𝑂(1)、原地排序：指针 i 和 j 使用常数大小的额外空间。
 

2、插入排序

插入排序（insertion sort）是一种简单的排序算法，它的工作原理与手动整理一副牌的过程非常相似。
具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。
插入排序的整体流程如下：
  1. 初始状态下，数组的第 1 个元素已完成排序。
  1. 选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。
  1. 选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。
  1. 以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。
notion image
  • 时间复杂度为 𝑂(𝑛2)
  • 空间复杂度为 𝑂(1)
 

3、快速排序

快速排序（quick sort）是一种基于分治策略的排序算法，运行高效，应用广泛。
快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。
选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。 循环执行步骤 2 ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。
notion image
时间复杂度：O(nlogn)
空间复杂度：O(n)
 

4、归并排序

归并排序（merge sort）是一种基于分治策略的排序算法，包含“划分”和“合并”阶段。
划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。
相关代码：
时间复杂度：O(nlogn)
空间复杂度：O(n)
 

5、堆排序

堆排序（heap sort）是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。
输入数组并建立小顶堆，此时最小元素位于堆顶。 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。 以上方法虽然可行，但需要借助一个额外数组来保存弹出的元素，比较浪费空间。在实际中，我们通常使用一种更加优雅的实现方式。
相关代码：
时间复杂度：O(nlogn)
空间复杂度：O(1)
 
前述这几种排序算法都属于“基于比较的排序算法”，它们通过比较元素间的大小来实现排序。此类排序算法的时间复杂度无法超越O(nlogn)。接下来，我们将探讨几种“非比较排序算法”，它们的时间复杂度可以达到线性阶。

6、桶排序

桶排序（bucket sort）是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。
算法流程 考虑一个长度为n的数组，其元素是范围[0,1)内的浮点数
初始化k个桶，将n个元素分配到k个桶中。 对每个桶分别执行排序（这里采用编程语言的内置排序函数）。 按照桶从小到大的顺序合并结果。
时间复杂度：O(n+k)
空间复杂度：O(n+k)
 

7、基数排序

将所有待比较数值（自然数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
三、实现步骤
（1）确定数组中的最大元素有几位（MAX）（确定执行的轮数）
（2）创建0~9个桶（桶的底层是队列），因为所有的数字元素都是由0~9的十个数字组成
（3）依次判断每个元素的个位，十位至MAX位，存入对应的桶中，出队，存入原数组；直至MAX轮结束输出数组。
notion image

小结

  • 冒泡排序通过交换相邻元素来实现排序。通过添加一个标志位来实现提前返回，我们可以将冒泡排序的最佳时间复杂度优化到 𝑂(𝑛) 。
  • 插入排序每轮将未排序区间内的元素插入到已排序区间的正确位置，从而完成排序。虽然插入排序的时间复杂度为 𝑂(𝑛^2) ，但由于单元操作相对较少，因此在小数据量的排序任务中非常受欢迎。
  • 快速排序基于哨兵划分操作实现排序。在哨兵划分中，有可能每次都选取到最差的基准数，导致时间复杂度劣化至 𝑂(𝑛^2) 。引入中位数基准数或随机基准数可以降低这种劣化的概率。尾递归方法可以有效地减少递归深度，将空间复杂度优化到 𝑂(log⁡𝑛) 。
  • 归并排序包括划分和合并两个阶段，典型地体现了分治策略。在归并排序中，排序数组需要创建辅助数组，空间复杂度为 𝑂(𝑛) ；然而排序链表的空间复杂度可以优化至 𝑂(1) 
  • 桶排序包含三个步骤：数据分桶、桶内排序和合并结果。它同样体现了分治策略，适用于数据体量很大的情况。桶排序的关键在于对数据进行平均分配。
  • 计数排序是桶排序的一个特例，它通过统计数据出现的次数来实现排序。计数排序适用于数据量大但数据范围有限的情况，并且要求数据能够转换为正整数。
  • 基数排序通过逐位排序来实现数据排序，要求数据能够表示为固定位数的数字。
 
notion image
 
 

时间复杂度小结

notion image
 
 

元运算

对于任何计算步骤，它的代价总是以一个时间常数为上界，而不管输入或者执行的算法，我们称该计算步骤为“元运算”。
如果算法中的一个元运算具有最高频率，所有其他元运算频率均在它的频率的常数倍内，则称这个元运算为基本运算。
在算法MERGE里元素赋值是基本运算
在分析搜索和排序算法时，元素的比较是基本运算
 

堆和不相交集

这里主要就是写出堆的几种基础操作，shift_up,shift_down,delete,insert
shift_up
 
shift_down
insert
delete
 
对于堆的创建，有两种方法
1.把数组里的每个元素依次插入到堆中，时间复杂度为O(nlogn)
2.将列表所有元素原封不动地添加到堆中，此时堆的性质尚未得到满足，然后倒序遍历堆（层序遍历的倒序），依次对每个非叶节点执行“从顶至底堆化”。时间复杂度为O(n)
 
然后就是堆排序

归纳法

整数幂的求解

算法1
算法2
算法3
 

分治法

  • 分治是一种常见的算法设计策略，包括分（划分）和治（合并）两个阶段，通常基于递归实现。
  • 判断是否是分治算法问题的依据包括：问题能否分解、子问题是否独立、子问题能否合并。
  • 归并排序是分治策略的典型应用，其递归地将数组划分为等长的两个子数组，直到只剩一个元素时开始逐层合并，从而完成排序。
  • 引入分治策略往往可以提升算法效率。一方面，分治策略减少了操作数量；另一方面，分治后有利于系统的并行优化。
  • 分治既可以解决许多算法问题，也广泛应用于数据结构与算法设计中，处处可见其身影。
  • 相较于暴力搜索，自适应搜索效率更高。时间复杂度为 𝑂(log⁡𝑛) 的搜索算法通常是基于分治策略实现的。
  • 二分查找是分治策略的另一个典型应用，它不包含将子问题的解进行合并的步骤。我们可以通过递归分治实现二分查找。
  • 在构建二叉树的问题中，构建树（原问题）可以划分为构建左子树和右子树（子问题），这可以通过划分前序遍历和中序遍历的索引区间来实现。
  • 在汉诺塔问题中，一个规模为 𝑛 的问题可以划分为两个规模为 𝑛−1 的子问题和一个规模为 1 的子问题。按顺序解决这三个子问题后，原问题随之得到解决。
 

动态规划

解题步骤：
第一步：思考每轮的决策（从当前状态到下一个状态采取的"行动"），然后根据决策定义状态，从而得到dp表（状态对应的子问题:从初始到任意一个状态,这个的解就是dp里对应状态的一个值）
动态规划和回溯过程可以描述为一个决策序列，而状态由所有决策变量构成。它应当包含描述解题进度的所有变量，其包含了足够的信息，能够用来推导出下一个状态。
每个状态都对应一个子问题，我们会定义一个dp表来存储所有子问题的解，状态的每个独立变量都是dp表的一个维度。从本质上看，dp表是状态和子问题的解之间的映射。
第二步：根据上一步的决策找出最优子结构，进而推导出状态转移方程
根据定义好的dp表，思考原问题和子问题的关系，找出通过子问题的最优解来构造原问题的最优解的方法，即最优子结构。
一旦我们找到了最优子结构，就可以使用它来构建出状态转移方程。
第三步：确定边界条件和状态转移顺序
边界条件在动态规划中用于初始化dp表，在搜索中用于剪枝。
状态转移顺序的核心是要保证在计算当前问题的解时，所有它依赖的更小子问题的解都已经被正确地计算出来。
总的来说就是找到dp表，然后用完整的状态转移方程来填表 动态规划本质是带记事本的暴力循环
 
更具体版：图解动态规划的解题四步骤_动态规划解题分为四步-CSDN博客
  • 定义子问题
  • 稍微接触过一点动态规划的朋友都知道动态规划有一个“子问题”的定义。什么是子问题？子问题是和原问题相似，但规模较小的问题。例如这道小偷问题，原问题是“从全部房子中能偷到的最大金额”，将问题的规模缩小，子问题就是“从 k 个房子中能偷到的最大金额”，用 f(k) 表示。
  • 写出子问题的递推关系
  • 这一步是求解动态规划问题最关键的一步。然而，这一步也是最无法在代码中体现出来的一步。在做题的时候，最好把这一步的思路用注释的形式写下来。做动态规划题目不要求快，而要确保无误。否则，写代码五分钟，找 bug 半小时，岂不美哉？
  • 确定 DP 数组的计算顺序
  • 在确定了子问题的递推关系之后，下一步就是依次计算出这些子问题了。在很多教程中都会写，动态规划有两种计算顺序，一种是自顶向下的、使用备忘录的递归方法，一种是自底向上的、使用 dp 数组的循环方法。不过在 普通的动态规划题目中，99% 的情况我们都不需要用到备忘录方法，所以我们最好坚持用自底向上的 dp 数组。DP 数组也可以叫”子问题数组”，因为 DP 数组中的每一个元素都对应一个子问题。如下图所示，dp[k] 对应子问题 f(k)，即偷前 k 间房子的最大金额。那么，只要搞清楚了子问题的计算顺序，就可以确定 DP 数组的计算顺序。对于小偷问题，我们分析子问题的依赖关系，发现每个 f(k) 依赖 f(k-1) 和 f(k−2)。也就是说，dp[k] 依赖 dp[k-1] 和 dp[k-2]。那么，既然 DP 数组中的依赖关系都是向右指的，DP 数组的计算顺序就是从左向右。这样我们可以保证，计算一个子问题的时候，它所依赖的那些子问题已经计算出来了。
 
完全背包问题：
0-1背包问题：
这两个背包问题的区别在于：
完全背包问题的转移方程为：dp[i,c] = max(dp[i-1],c,dp[i,c-wgt[i-1]]+val[i-1])
0-1背包问题的转移方程为：dp[i,c] = max(dp[i-1,c],dp[i-1,c-wgt[i-1]]+val[i-1])
 
  • 0-1 背包的状态定义为前 𝑖 个物品在容量为 𝑐 的背包中的最大价值。根据不放入背包和放入背包两种决策，可得到最优子结构，并构建出状态转移方程。在空间优化中，由于每个状态依赖正上方和左上方的状态，因此需要倒序遍历列表，避免左上方状态被覆盖。
  • 完全背包问题的每种物品的选取数量无限制，因此选择放入物品的状态转移与 0-1 背包问题不同。由于状态依赖正上方和正左方的状态，因此在空间优化中应当正序遍历。
 
最后总结一下：
1、首先通过题目的问题，写出子问题，比如问你N个石堆，你就想N-1个石堆
2、然后用子问题来定义状态，比如：状态 [𝑖,𝑎] 对应的子问题为：前 𝑖 种硬币能够凑出金额 𝑎 的最少硬币数量，记为 𝑑𝑝[𝑖,𝑎] 。
3、找到dp[i]和dp[i-1]以及其他的关系，也可以说是状态转移顺序，一般都是从右向左来递推的。
notion image
 
4、推导出状态转移方程
5、确定边界条件
 

并查集(不相关集)

原文：[算法拾级]不相交集(并查集) - 知乎 (zhihu.com)
通用描述如下，不相交集是一种描述不相交集合的数据结构，若一个问题涉及多个元素，可划归不同集合，同属一个集合内的元素等价（即可用任意一个元素作为代表），不同集合内的元素不等价。当我们问某些元素是否等价时，例如亲戚问题中问两人否互为亲戚关系时，就可以用不相交集来解决。这类问题的初始状态通常是每一个元素构成一个单元素集合，后续通过合并操作将等价元素归入一个集合中。因此处理过程中通常要用到查询（元素属于哪个集合，用于决定是否要执行合并）及合并集合的操作。故此，不相交集也叫并查集，“不相交”描述的是问题对象构成集合之后不同集合不相交的状态，“并查”描述的是处理问题时的操作。
1.初始化 init
2.查找并且记录”祖先”到记事本里 find
3.合并 union
 
 
 

贪心算法(第 15 章   贪心 - Hello 算法 (hello-algo.com))

贪心算法和动态规划的比较

动态规划中，父问题结果的得出需要它的子问题作为前提。
贪心选择中,一个子问题并不依赖于另一个子问题,贪心算法具有“贪心选择性”。
相较于动态规划，贪心算法的使用条件更加苛刻，其主要关注问题的两个性质。
  • 贪心选择性质：只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解。
  • 最优子结构：原问题的最优解包含子问题的最优解。

贪心算法解题步骤

贪心问题的解决流程大体可分为以下三步。
  1. 问题分析：梳理与理解问题特性，包括状态定义、优化目标和约束条件等。这一步在回溯和动态规划中都有涉及。
  1. 确定贪心策略：确定如何在每一步中做出贪心选择。这个策略能够在每一步减小问题的规模，并最终解决整个问题。
  1. 正确性证明：通常需要证明问题具有贪心选择性质和最优子结构。这个步骤可能需要用到数学证明，例如归纳法或反证法等。
确定贪心策略是求解问题的核心步骤，但实施起来可能并不容易，主要有以下原因。
  • 不同问题的贪心策略的差异较大。对于许多问题来说，贪心策略比较浅显，我们通过一些大概的思考与尝试就能得出。而对于一些复杂问题，贪心策略可能非常隐蔽，这种情况就非常考验个人的解题经验与算法能力了。
  • 某些贪心策略具有较强的迷惑性。当我们满怀信心设计好贪心策略，写出解题代码并提交运行，很可能发现部分测试样例无法通过。这是因为设计的贪心策略只是“部分正确”的，上文介绍的零钱兑换就是一个典型案例。
为了保证正确性，我们应该对贪心策略进行严谨的数学证明，通常需要用到反证法或数学归纳法。
然而，正确性证明也很可能不是一件易事。如若没有头绪，我们通常会选择面向测试用例进行代码调试，一步步修改与验证贪心策略。
 

贪心算法正确性证明的方法

1.替换法（背包问题）
用贪心算法得出的解(x1,x2,x3,…,xn)和最优解(y1,y2,y3,…,yn)中的元素依次进行比较，如果元素xi和yi相同，则将最优解中的yi替换成xi，显然替换后的解还是最优解;如果不同，还是将yi替换成xi，但此时需要证明替换后的解依然是最优解.
2.反证法证明（单源最短路径）
假设算法得到的解不是最优解，然后通过推导与矛盾的结论来证明假设是错误的，即算法得到的解是最优解。
3.数学归纳法证明（最小生成树）
对于问题规模进行归纳，证明算法对于所有规模的输入都能得到最优解。
 
在选择使用贪心算法还是动态规划来解决问题时，关键在于理解问题的性质和所需解决的目标。这两种算法各有其优势和适用场景，以下是一些标准和考虑因素，可以帮助你决定使用哪种方法：

贪心算法

贪心算法在每一步都采取在当前看来最优的选择，希望通过局部最优的选择来达到全局最优。它通常用于以下情形：
  1. 问题具有贪心选择性质：可以通过局部最优决策构造全局最优解。这意味着一个问题的整体最优解可以通过一系列局部最优的选择得到。
  1. 问题具有最优子结构：问题的最优解包含其子问题的最优解，但与动态规划不同，贪心算法不重新考虑先前做出的选择。
  1. 简单高效：贪心算法通常比动态规划更简单，执行效率更高，因为它不需要考虑多种可能的解决方案路径。
  1. 应用场景：贪心算法常用于求解最小生成树、哈夫曼编码等问题。

动态规划

动态规划适用于有重叠子问题和最优子结构性质的问题，它通过构建子问题的解决方案来找到整个问题的解决方案。适用场景包括：
  1. 重叠子问题：问题可以分解为子问题来解决，且子问题会重复出现多次。
  1. 最优子结构：问题的最优解包含其子问题的最优解，需要保存这些子问题的解，以便复用。
  1. 可以通过递归实现：动态规划问题通常可以用递归算法来描述，但为了提高效率，通常使用迭代加表格（或其他数据结构）来保存中间结果。
  1. 应用场景：动态规划用于解决背包问题、编辑距离、最长公共子序列等问题。

如何选择？

  • 分析问题是否能够分解为子问题，并且这些子问题是否具有重叠性。如果答案是肯定的，并且你需要保存这些子问题的解来避免重复计算，那么动态规划可能是合适的选择。
  • 考虑是否每个步骤的决策都依赖于之前的状态。对于那些一旦作出决策就不需要再考虑以前的决策的问题，贪心算法可能是更好的选择。
  • 评估问题的规模和复杂度。贪心算法通常在时间和空间效率上优于动态规划，因为它不需要存储大量的状态信息。
总的来说，选择贪心算法还是动态规划取决于问题的特性和所需的解决方案的精确性。在某些情况下，尝试实现并比较这两种方法的结果也是一种有效的策略。
 

例题：

1. 最大化存储文件的数量
这个问题要求在给定的磁盘容量限制下，存储尽可能多的文件。其主要目标是最大化文件的数量而不是磁盘的使用率或其他因素。对此问题，贪心算法是非常合适的选择：
  • 贪心选择：从最小的文件开始存储，因为小文件占用空间少，可以让你有更多的剩余空间来存储其他文件。
  • 最优子结构：每次选择最小的文件后，剩余问题（减少的空间和待选择的文件）仍是一个相同类型的问题。
  • 算法实现：按文件大小排序，然后从最小的开始尝试存入磁盘，直到没有足够空间为止。
在这种情况下，贪心算法不仅简单高效，而且能够确保达到存储尽可能多文件的目标。
2. 最大化磁盘空间的使用（最小化未使用空间）
如果目标是最大化磁盘空间的使用或最小化未使用的磁盘空间，问题更类似于传统的背包问题，其中不仅仅是要存储尽可能多的文件，还要尽可能填满磁盘空间。这种情况更适合使用动态规划：
  • 重叠子问题：解决方案需要处理每个小于等于磁盘容量的所有可能空间大小的最优填充方式。
  • 最优子结构：解决整个磁盘容量的最优填充问题需要依赖于解决其子问题的结果（较小的磁盘容量的最优填充）。
  • 算法实现：使用动态规划表来记录每个容量下的最大文件存储总和，逐步构建直至整个磁盘容量。
在这种情况下，动态规划能够考虑各种大小组合的文件，以找到最大限度利用磁盘空间的最佳组合，这是贪心算法难以做到的。

总结

这两种算法的选择基于问题的具体需求：如果问题仅关注最大化文件数量，贪心算法简单且有效；如果问题需要优化磁盘空间的使用，动态规划提供了一个全面审视所有可能性的方法。正确地理解和定义问题的目标是选择最合适算法的关键。
 
更进一步的解释：

1. 最大化存储文件的数量

问题：有一定数量的文件和一个固定大小的磁盘。你需要存储尽可能多的文件。
解决方案：使用贪心算法。这种情况下，贪心算法是理想的选择，因为我们的目标是简单地最大化数量。贪心算法在这里的策略是“选择最小的文件先存”，这样做的逻辑是：较小的文件占用较少的空间，这样可以留更多的空间给其他文件。
为什么有效：因为每次选择最小的文件，你可以确保在磁盘容量允许的情况下放入最多数量的文件。这个策略确保了在每一步选择中，你都保留了最大的剩余空间。

2. 最小化未使用的磁盘空间

问题：同样是有一定数量的文件和一个固定大小的磁盘，但这次你需要尽量使用完所有的磁盘空间，即尽量不要留下未使用的空间。
解决方案：使用动态规划。这是因为你需要考虑如何组合文件，以便最大限度地填充磁盘空间。这类似于“填充背包”的问题，其中你尝试在不超过背包容量的情况下填充最大价值的物品，只不过在这里“价值”是文件所占的空间。
为什么有效：动态规划可以考虑所有可能的文件组合，查找哪种组合最接近完全利用磁盘容量。这是贪心算法做不到的，因为贪心算法只考虑当前最优选择，而不是全局最优。

如何实施这些算法

  • 对于贪心算法：
      1. 将所有文件按大小进行排序。
      1. 从最小的文件开始，依次检查每个文件是否能放入剩余空间中。
      1. 继续此过程，直到没有足够空间为下一个文件。
  • 对于动态规划：
      1. 创建一个数组，其大小为磁盘容量加一（从0到C）。
      1. 数组的每个位置记录使用该容量能达到的最大文件存储总和。
      1. 遍历每个文件，更新数组值，反映如果添加这个文件会怎样。
 

动态规划算法和分治算法和贪心算法的区别

首先，分治算法和动态规划算法都采用递归的策略解决问题。分治算法通过将问题分解为子问题并递归地求解子问题来解决问题，而动态规划则通过保存子问题的解来避免重复计算。这两种算法都适用于处理大规模数据和复杂问题，但动态规划更注重于优化重叠子问题的求解过程。
其次，贪心算法与前两者有所不同。贪心算法的核心在于作出局部最优的选择来推导全局最优解。贪心算法通常适用于具有最优子结构性质的问题，它在每一步选择中都追求当前状态下最好的结果，以期达到全局最优。但请注意，贪心算法并不保证能得到最优解，尤其在问题复杂度较高的情况下。
接下来，我们通过一个具体的案例来进一步理解这三种算法的应用。假设我们有一个任务是找出一个无向图中的最长路径。首先，我们可以使用分治算法将图划分为若干个子图，分别求解子图的最长路径，然后将子图的解合并以获得原图的最长路径。其次，我们也可以使用动态规划来解决这个问题。我们定义一个状态数组dp[i]，其中dp[i]表示从起点到第i个顶点的最长路径长度，然后利用状态转移方程逐步求解dp数组的值。最后，贪心算法也可以用于求解最长路径问题。我们可以从起点开始，每次选择一条可以到达的边，使路径长度增加最多，直到无法再增加路径长度为止。
分治算法通过将问题分解为子问题并递归地求解子问题来解决问题；动态规划则通过保存子问题的解来避免重复计算，优化重叠子问题的求解过程；贪心算法则通过在每一步选择中都追求当前状态下最好的结果来推导全局最优解。在实践中，我们应根据具体问题的性质和规模选择合适的算法策略。
 

NP类问题和P类问题

定义非确定性算法：设A是求解问题∏的一个算法，如果算法A以猜测并验证的方式工作，则称算法A是非确定性算法。
定义(NP类问题): 如果对于判定问题∏，存在一个非负整数k，对于输入规模为n的实例，能够以O(n^k)的时间运行一个非确定性算法，得到yes/no的答案，则该判断问题∏ 是一个NP类问题。
定义(确定性算法)：设A是求解问题П的一个算法。如果在算法执行过程中每一步都只有一种选择，则称A是确定性算法。
定义(P类问题)：如果对于某个判定问题П，存在一个非负整数k，对于输入规模为n的实例，能以 O(n^k) 时间运行一个确定性算法，得到yes或no的答案，则该判定问题是一个P类问题。
定义(NP完全问题): 令∏是一个判定问题，如果问题∏属于NP类问题，并且对NP类问题中的每一个问题∏′，都有∏′∝∏，则称判定问题∏是一个NP完全问题(NP complete problem, NPC)。
 
 
P类问题和NP类问题的异同 ➢ 共同点：
  1. 都是判定问题。2. 都是多项式时间的。
➢ 不同点：
  1. P 类问题可以用确定性算法解决，NP 类问题可以用非确定性算法解 决。
  1. P 类问题可以在多项式时间内求得答案，NP 类问题只能在多项式时 间内验证。
 

回溯算法

1.框架代码
notion image
notion image
2.优点与局限性
回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。这种方法的优点在于能够找到所有可能的解决方案，而且在合理的剪枝操作下，具有很高的效率。
然而，在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受。
  • 时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶。
  • 空间：在递归调用中需要保存当前的状态（例如路径、用于剪枝的辅助变量等），当深度很大时，空间需求可能会变得很大。
即便如此，回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题，由于无法预测哪些选择可生成有效的解，因此我们必须对所有可能的选择进行遍历。在这种情况下，关键是如何优化效率，常见的效率优化方法有两种。
  • 剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间。
  • 启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径。
 
 
1、14个函数进行排序
2、分治，寻找第K小元素
3、动态规划，一个关于x1x2x3……xn
4、回溯，求哈密尔顿回路
5、背包问题，贪心算法，还有正确性证明
6、归纳法，整数幂
上一篇
V2Board搭建教程
下一篇
前端3件套学习
评论
Loading...