算法的下限和上限理论

小鱼儿 2023-10-14 07:17 15阅读 0赞

下限和上限理论是一个数学概念，涉及在给定某些约束或条件的情况下找到某个量的最小和最大可能值。它经常用于优化问题，其目标是找到受某些约束的函数的最大值或最小值。

用数学术语来说，一组数字的下界是该组中最小的数字，而上限是最大的数字。如果一个集合有下界和上限，则称该集合是有界的。  
下限和上限理论也可用于确定变量可能值的范围。例如，如果我们知道某个变量必须在0和1之间，我们可以说它的下限是0，上限是1。  
下限和上限的概念与下确界和上界的概念密切相关。集合的下确界是集合的最大下界，上界是集合的最小上界。  
总体而言，下限和上限理论是数学分析、优化和决策中的重要工具，因为它使我们能够确定某个量的可能值的范围并确定该范围内的最优值。  
下限和上限理论提供了一种找到解决问题的最低复杂度算法的方法。在理解理论之前，首先让我们简单了解一下什么是下限和上限。

下界 –  
令 L(n) 为算法 A（例如）的运行时间，如果存在两个常数 C 和 N 使得 L(n) >= C\*g，则 g(n) 是 A 的下界(n) 对于 n > N。算法的下界由称为Big Omega （或简称 Omega）的渐近符号表示。

上限 –  
令 U(n) 为算法 A（例如）的运行时间，如果存在两个常数 C 和 N 使得 U(n) <= C\*g，则 g(n) 是 A 的上界(n) for n > N。算法的上限由称为Big Oh(O) （或简称 Oh）的渐近符号表示。  
1.下界理论：  
根据下界理论，对于一个算法的下界L(n)，不可能有任何其他算法（针对常见问题）的时间复杂度小于L(n)用于随机输入。此外，在最坏的情况下，每个算法必须至少花费 L(n) 时间。请注意，这里的 L(n) 是所有可能算法中的最小值，具有最大的复杂性。  
下界对于任何算法都非常重要。一旦我们计算出它，我们就可以将它与算法的实际复杂度进行比较，如果它们的顺序相同，那么我们就可以声明我们的算法是最优的。因此，在本节中，我们将讨论寻找算法下界的技术。

请注意，我们的主要动机是获得一种最佳算法，即上界与其下界相同的算法 (U(n)=L(n))。归并排序是最优算法的常见示例。

平凡下界 –  
这是找到下界的最简单方法。根据输入的数量和产生的输出的数量可以轻松观察到的下界称为平凡下界。

示例： nxn 矩阵的乘法，其中，

输入：对于 2 个矩阵，我们将有 2n 2 个输入  
输出：1 个 nxn 阶矩阵，即 n 2 个输出  
在上面的例子中，很容易预测下界是 O(n 2 )。

计算模型 -  
该方法适用于所有基于比较的算法。例如，在排序时，我们必须比较列表中的元素，然后对它们进行相应的排序。搜索的情况类似，因此我们可以在这种情况下实现相同的效果。现在我们将看一些示例来了解它的用法。

有序搜索——  
这是一种列表已经排序的搜索类型。  
示例 1： 线性搜索  
说明 –  
在线性搜索中，我们将键与第一个元素进行比较，如果不匹配，我们将其与第二个元素进行比较，依此类推，直到我们检查第 n 个元素。否则我们就会以失败告终。

示例 2： 二分搜索  
说明 –  
在二分搜索中，我们根据键检查中间元素，如果它更大，我们搜索前半部分，否则我们检查后半部分并重复相同的过程。  
下图展示了在由 4 个元素组成的数组中进行二分查找  
![在这里插入图片描述][029fcfcb982f4f5b8013a45be50debdc.png]  
计算下限：最大比较次数为 n。设树中有 k 层。

节点数量为 2 k -1  
在大小为 n 的列表中对元素进行任何基于比较的搜索时，节点数量的上限将为 n，因为在最坏情况下最多有 n 次比较 2 k -1  
每个级别将进行 1 次比较，因此不会。比较次数 k≥|log 2 n|  
因此，来自 n 个元素的列表的任何基于比较的搜索的下限不能小于 log(n)。因此我们可以说二分查找是最优的，因为它的复杂度是 θ(log n)。

排序 –  
下图是由 3 个元素排序组合形成的树的示例。  
![在这里插入图片描述][0dd71e7cd0a84d54b1e197662b9ac56a.png]  
示例 –对于 n 个元素，使用计算模型查找下界。

解释 –  
对于 n 个元素，我们总共有 n 个！组合（叶节点）。（参见图，总的组合是3！或6）而且，很明显，形成的树是二叉树。图中的每个级别都表示一个比较。设 k 个级别 => 2 k是满二叉树中叶节点的总数，因此在这种情况下我们有 n!≤2 k。

由于上例中的 k 是比较次数，因此通过计算模型下界 = k。

现在我们可以说，

[029fcfcb982f4f5b8013a45be50debdc.png]: https://img-blog.csdnimg.cn/029fcfcb982f4f5b8013a45be50debdc.png
[0dd71e7cd0a84d54b1e197662b9ac56a.png]: https://img-blog.csdnimg.cn/0dd71e7cd0a84d54b1e197662b9ac56a.png