下界理论

下界理论的概念是基于计算执行算法所需的最短时间，这被称为下界理论或基本界理论。

下界理论使用多种方法/技术来找出下界。

概念/目的： 主要目的是计算执行算法所需的最小比较次数。

技术

下界理论使用的技术包括：

1. 比较树。
2. Oracle 和对抗论证
3. 状态空间方法

1. 比较树

在比较排序中，我们仅使用元素之间的比较来获取有关输入序列（a1; a2......an）的顺序信息。

给定a_i,a_j从(a₁, a₂.....a_n)我们执行以下比较之一

• a_i < a_j       小于
• a_i ≤ a_j       小于或等于
• a_i > a_j       大于
• a_i ≥ a_j       大于或等于
• a_i = a_j       等于

为了确定它们的相对顺序，如果我们假设所有元素都是不同的，那么我们只需要考虑a_i ≤ a_j，“=”被排除在外，&，≥,≤,>,< 是等价的。

考虑对三个数字 a1、a2 和 a3 进行排序。 有 3！ = 6 种可能的组合

基于比较的算法定义了一个决策树。

决策树： 决策树是一个完整的二叉树，它显示了元素之间由适当的排序算法在给定大小的输入上执行的比较。 算法的控制、数据移动和所有其他条件都被忽略。

在决策树中，将有一个长度为 n 的数组。

所以，总叶子数将是 n！（即比较的总数）

如果树高为 h，那么一定有

    n! ≤2n (tree will be binary)

以比较 a1、a2 和 a3 为例。

左子树将为真条件，即 a_i ≤ a_j

右子树将为假条件，即 a_i > a_j

图：决策树

因此，从上面我们得到

N! ≤2n   

两边取对数

二分查找的比较树

示例： 假设我们有一个项目列表，其位置如下

最后一个中点是

因此，我们将考虑所有中点，并通过逐步中点来制作一棵树。

粗体字母是这里的中点

根据中点，这棵树将是

步骤1： 内部节点最多 k 级的最大节点数为 2^k-1

例如

 2k-1
 23-1= 8-1=7
Where k = level=3

步骤2： 比较树中的最大内部节点数为 n!

注意：这里的内部节点是叶子。

步骤3： 从条件1 & 条件 2 我们得到

N! ≤ 2k-1
 14 < 15
 Where N = Nodes

步骤4： 现在，n+1 ≤ 2^k

这里，内部节点将始终小于二分查找中的 2^k。

步骤 5

n+1<= 2k
   Log (n+1) = k log 2
 k >= 
  k >=log2(n+1)

步骤 6

步骤 7

T (n) >=log2(n+1)

这里，使用二分查找执行 n 项搜索任务的最小比较次数

2. Oracle 和对抗论证

获得下限的另一种技术包括使用“oracle”。

给定一些估计模型，例如比较树，oracle 告诉我们每次比较的结果。

为了推导出一个好的下界，oracle 尽最大努力使算法尽可能努力地工作。

它通过决定作为下一次分析的结果，即确定最终答案需要最多的工作的结果来实现这一点。

通过跟踪完成的工作，可以推导出问题的最坏情况下的下界。

示例：（合并问题） 给定集合 A (1: m) 和 B (1: n)，其中 A 和 B 中的信息已排序。 考虑用于组合这两个集合以得到单个排序集合的算法的下界。

假设所有 m+n 个元素都是特定的，并且 A (1) < A (2) < ....< A (m) 且 B (1) < B (2) < ....< B (n)。

基本组合学告诉我们，A 和 B 可以合并在一起的方式有 C ((m+n), n)) 种，同时仍然保持 A 和 B 中的顺序。

因此，如果我们需要比较树作为组合算法的模型，那么将有 C ((m+n), n)) 个外部节点，因此任何基于比较的合并算法至少需要 log C ((m+n), m) 次比较。

如果我们让 MERGE (m, n) 作为用于将 m 个项目与 n 个项目合并的最小比较次数，那么我们有不等式

当 m 比 n 小得多时，上限和下限会迅速拉开距离。

3. 状态空间方法

1. 状态空间方法是一组规则，用于显示算法可以从单个比较的给定状态假设的可能状态（n 元组）。

2. 一旦给出了状态转换，就可以通过论证使用更少的转换无法达到完成状态来推导出下界。

3. 给定 n 个不同的项目，找到获胜者和失败者。

4. 目的：状态改变时计数，这就是状态空间方法的目的。

5. 在这种方法中，我们将通过计算状态变化的数量来计算比较的数量。

6. 使用状态空间方法分析问题，以找出最小和最大的项目。

7. 状态：它是属性的集合。

8. 通过它，我们解决了两种类型的问题

1. 从元素数组中找到最大和最小元素。
2. 从元素数组中找出最大和第二大元素。

9. 对于最大的项目，我们需要 7 次比较，那么第二大的项目是什么？

Now we count those teams who lose the match with team A 
    Teams are: B, D, and E
So the total no of comparisons are: 7
Let n is the total number of items, then
    Comparisons = n-1 (to find the biggest item) 
No of Comparisons to find out the 2nd biggest item = log2n-1

10. 在这里，比较次数等于算法执行期间状态变化的数量。

示例： 状态 (A, B, C, D)

1. 永远无法比较的项目数。
2. 获胜但从未失败的项目数（最终获胜者）。
3. 失败但从未获胜的项目数（最终失败者）
4. 有时失败 & 有时获胜的项目数。

首先，A、B 比较或匹配它们。 A 获胜，在 C、D 中，C 获胜等等。 我们可以假设 B 获胜等等。 我们可以假设 B 代替 A 获胜，它可以是任何取决于我们自己的东西。

在 Phase-1 中有 4 个状态
如果团队是 8 个，那么有 4 个状态
就像 n 个团队，有 n/2 个状态。

4 在 C-State 中是常数，因为 B、D、F、H 是从未获胜的失败团队。

因此，在 Phase-2 中有 3 个状态，
如果 n 是 8，那么状态是 3
如果 n 个团队是 状态。

Phase-3： 这是一个阶段，其中考虑 C-State 下的团队，并且它们之间将进行比赛，以找出根本没有获胜的团队。

在这个结构中，我们将向上移动以表示谁在比赛后没有获胜。

这里 H 是根本没有获胜的团队。 通过此，我们实现了我们的第二个目标。

因此，在 Phase -3 中有 3 个状态
如果 n 个团队是 状态

注意：所有状态值的总和始终等于“n”。

因此，通过添加所有阶段的状态，我们将得到：-

Phase1 + Phase 2 + Phase 3

假设我们有 8 个团队，那么 存在（至少）状态以找出哪个团队永远不会获胜。

因此，方程为

下界（L (n)）是特定问题的属性，即排序问题，矩阵乘法，而不是解决该问题的任何特定算法。

下界理论表明，对于任意输入，没有计算可以以小于 (L (n)) 倍的单位执行该活动，即，对于每个基于比较的排序算法，在最坏的情况下必须至少花费 L (n) 时间。

L (n) 是最大的整体可行的计算基准。

简单下界用于产生最佳替代方案的界限，以计算问题输入中必须准备的元素数量以及需要生成的输出项目数量。

下界理论是一种已用于以最有效的方式建立给定算法的方法。 这是通过发现一个函数 g (n) 来完成的，该函数是任何算法解决给定问题所必须花费的时间的下界。 现在，如果我们有一个算法的计算时间与 g (n) 的顺序相同，那么我们知道渐近地我们无法做得更好。

如果 f (n) 是某个算法的时间，那么我们写 f (n) = Ω (g (n)) 表示 g (n) 是 f (n) 的下界。 如果存在正的常数 c 和 n0，使得对于所有 n > n0，|f (n)| >= c|g (n)| ，则可以正式编写此方程。 此外，为了在常数因子内开发下界，我们更自觉地确定尽可能更精确的界限。

推导良好的 下界 比设计高效的算法更具挑战性。 这是因为下界陈述了解决问题的 *所有可能算法* 的事实。 通常，我们无法枚举和分析所有这些算法，因此下界证明通常很难获得。