下界和上界理论提供了一种寻找最低复杂度算法来解决问题的方法。在理解这个理论之前，首先让我们看一下到底什么是下界和上界。
- 下限 -
设L(n)为算法A的运行时间，则g(n)为下限如果存在两个常数C和N，使L(N) >= C*g(N)对N > N大欧米茄（或只是omega）。 - 上限 -
设U(n)为算法A的运行时间，则g(n)为上限如果存在两个常量c和n，使得n> n的u（n）<= c * g（n）。算法的上限被称为渐近符号大哦(O)（或只是哦）。
1.下限理论：
根据下界理论，对于一个算法的下界L(n)，对于随机输入，不可能有任何其他算法(对于一个常见问题)的时间复杂度小于L(n)。在最坏的情况下，每个算法必须花费至少L(n)的时间。请注意这里的L（n）是所有可能的算法的最大值，最大复杂度。
下界对于任何算法都是非常重要的。一旦我们计算出来，我们就可以把它和算法的实际复杂度进行比较，如果它们的顺序相同，那么我们就可以声明我们的算法是最优的。在这一节中，我们将讨论寻找算法下界的技术。
请注意我们的主要动机是得到一个最优算法，它的上界和下界相同(U(n)=L(n))。合并排序是最优算法的一个常见例子。
平凡下界
这是求下界最简单的方法。下界可以很容易地观察到的基础上输入的数量和产出的数量被称为平凡下界。
例子:n x n矩阵的乘法，在哪里，
输入:对于2个矩阵，我们有2n2输入输出: 1阶n × n矩阵，即n2输出
在上面的例子中，它易于预测下限是o（n2)。
计算模型,
该方法适用于所有基于比较的算法。例如，在排序时，我们必须比较列表中的元素，然后对它们进行相应的排序。搜索的情况也类似，因此我们可以在本例中实现相同的方法。现在我们来看一些例子来理解它的用法。
订购搜索 -
这是一种搜索类型，其中列表已经排序。
示例1:线性搜索
解释,
在线性搜索中，我们将键值与第一个元素进行比较，如果不匹配，我们就与第二个元素进行比较，以此类推，直到我们对第n个元素进行检查。否则我们将以失败告终。
实施例-2：二分查找
解释,
在二进制搜索中，我们检查中间元素对钥匙，如果我们搜索前半部分我们检查下半部分并重复相同的过程。
下图演示了在一个由4个元素组成的数组中进行二分搜索
计算下界:比较的最大值是n。设树中有k层。
- 节点数量将是2k-1
- 对于大小为n的列表中的元素，任何基于比较的搜索中节点no的上界都是n，因为在最坏情况场景2中有最大n次比较k-1
- 每个关卡将进行1次比较。比较k≥|日志2n |
因此，来自N个元素列表的任何基于比较的搜索的下限不能小于日志（n）。因此，我们可以说二进制搜索是最佳的，因为它的复杂性是θ（log n）。
排序,
下图是在分类组合中形成的树的示例，其中3个元素。
的例子,对于n个元素，用计算模型求下界。
解释,
对于n个元素，我们有n个元素!组合(叶子节点)。(如图所示，总共有3种组合!或者6)很明显，形成的树是一棵二叉树。图中的每一层都表示一种比较。设有k个级别=> 2k在这种情况下，完整二叉树中的叶节点的总数是我们有n！≤2k。
由于上述例子中的k是比较的no，因此通过计算模型，较低的键= k。
现在我们可以这么说，n !≤2T (n)因此,T (n) > | o (log n) !| = > n !< = nn因此,o (log n) !< = o (log n)n双方占用天花板功能，我们得到|-o (log n)n|> = |-log n！-|因此复杂性变为θ（lognn)或Θ(nlogn)
用下键理论解决代数问题:
- 直线程序 -
没有任何环路或控制结构的程序版本的类型称为直线程序。例如，
C
/ /求和号
总和(a, b)
{
//没有循环，没有控制结构
c: = a + b;
返回
c;
}
|
- 代数问题,
与代数有关的问题，如解方程，不等式等，属于代数问题。例如，解ax方程2+ BX + C具有简单的编程。
C
Algo_Sol(a, b, c, x)
{
/ /赋值1
v：= a * x;
/ /赋值1
v: = v + b;
/ /赋值1
v：= v * x;
/ /赋值1
ans：= v + c;
返回
答;
}
|
这里解决的复杂性是4(不包括返回)。
上面的例子向我们展示了一种简单的方法来解一个2次多项式的方程，即4，因此对nTH.程度多项式我们将具有o的复杂性（n2)。
让我们通过一个算法来演示。
例子:一个nxn+ A.N-1xN-1+ A.N-2xN-2+……+一个1x +一个0是n次的多项式。
C
鲍
（x，n）
{
P：= 1;
//从1到n的循环
为
我：= 1到n
p：= p * x;
返回
P;
}
多项式(A, x, n)
{
int
p，v：= 0;
为
我：= 0到n
//循环内从0到n的循环
v:= v + A[i]*
鲍
(x,我);
返回
v;
}
|
循环循环=>复杂度= o（n2);
现在要找到一个最佳算法，我们需要在此处找到下限（根据下限理论）。根据下界理论，解决上述问题的最佳算法是具有复杂性O（n）的算法。让我们使用下限来证明本定理。
定理:证明求解n次多项式的最优算法是O(n)
证明：简化算法的最佳方法是将多项式分解为若干个直线问题，使问题变得不那么复杂。
= >nxn+ A.N-1xN-1+ A.N-2xN-2+……+一个1x +一个0可以写成，(…)anx +一个N-1）x + .. + a2) x +一个1) x +一个0算法是，v=0 v=v+anv = v * x v = v + aN-1v = v * x……v = v + a1v = v * x v = v + a0
C
多项式(A, x, n)
{
int
p, v = 0;
循环执行n次
为
我= n到0
v =（v + a [i]）* x;
返回
v;
}
|
显然，这段代码的复杂度是O(n)。这种解方程的方法叫做霍纳法。这就是下界理论适用的地方，并给出最优算法的复杂度为O(n)。
2.上界理论:
根据上限理论，对于算法的上限U（n），我们可以始终在大多数U（n）时间内解决问题。通过已知的算法拍摄的时间来解决更糟糕的案例输入给我们提供上限。
关注读者!现在不要停止学习。掌握所有重要的DSA概念DSA自定进度课程以学生友好188bet2021欧洲杯的价格，成为工业准备。要完成您的准备，请从学习语言到DS ALGO等等，请参阅完成面试准备课程金宝搏188beat。
