https://www.youtube.com/playlist?list=PLkFD6_40KJIyKLUW_4cm44mIdXSUpZry3
算法是一种明确定义的计算任务完成过程。常见算法包括谷歌地图找路、加法等。
正确性。算法输出结果必须正确。
效率。可以考虑时间效率、内存效率、并行度等方面的效率。
第一步设计正确算法,然后考虑效率。
加法问题输入是两个以10进制表示的正整数。
时间复杂度O(10^n),效率很低。
时间复杂度O(n),一般在小学就会的最常用加法算法。
每个位数都影响结果,不能忽略任意一位,所以加法下界Ω(n)。不可能有更快的非均匀算法。
以其他进制表示数字可能增加编码复杂度,不具有统一性。
本节主要介绍了算法概念、设计原则及常用加法算法。乘法算法将在未来课时详细讨论。
许多学生没有注意到讨论小组有排队规则。如果要加入讨论,需要去官方网站登记名单或排队。助教会优先解答概念性问题而不是作业问题。
上次讨论了算数运算的效率,特别是加法和乘法。我们知道相比标准算法,乘法有更快的算法。
讨论计算斐波那契数列的四种算法。
算法1:递归实现。时间复杂度为指数级。
算法2:迭代实现。时间复杂度线性的O(n)。
可以用矩阵快速求斐波那契数列。定义2×2矩阵A,向量V={F1,F0},则AnV={Fn+1,Fn}。
通过重复平方,可以在O(logn)时间内计算An,得到快速指数算法。
最后概括经典分治思想,以及用主定理分析递归复杂度。
矩阵乘法的传统做法是使用三重循环,时间复杂度是O(n^3)。我们可以使用分治思想来降低时间复杂度。
我们将两个n×n矩阵X和Y分别划分为4个大小为n/2×n/2的块。然后根据块矩阵乘法公式,可以表达Z矩阵为这些块的线性组合。
例如,Z矩阵左上角块可以表示为A块和E块的点积加B块和G块的点积。
这样我们将一个矩阵乘法问题分解成8个子问题,每个子问题是两块n/2×n/2矩阵的乘法。
根据主定理,这种递归关系对应的时间复杂度是O(n^3)。
1969年,斯特劳森提出一种改进算法,将递归关系中的乘法次数从8降低到7。
他定义了7个参数P1到P7,每个参数表示一个n/2×n/2矩阵乘法。然后证明通过这7个参数的线性组合,就可以恢复原问题的答案Z矩阵。
这导致递归关系中的乘法次数下降为7。根据主定理,这种情况下的时间复杂度是O(n^(log27))≈O(n^{2.807}) better than O(n^3)
1987年,Coppersmith和Winograd使用更复杂的方法,将时间下限进一步降低到O(n^{2.375})。
之后有一系列工作通过细致的分析和优化逐步提高这个下限,现阶段的最优算法是O(n^{2.3728639})。
但与整数乘法相比,矩阵乘法的时间下限仍没有达到线性阶。这也成为一个开放性研究问题。
多项式乘法问题被定义为:给定两个多项式a(x)和b(x),每个多项式的最大 degree都小于D,a(x) 可以表示为 a0 + a1x + … + aD-1x^(D-1), b(x)可以表示为 b0 + b1x + … + bD-1x^(D-1)。目的是计算c(x)=a(x)*b(x)的系数向量。
c(x)的最大degree为2D-2。定义n=2D-1,这样a(x),b(x),c(x)都可以看作degree小于n的多项式。
c(x)的各项系数可以表示为:
Ck = Σ_{j=0}^{k} aj*b_{k-j}
其中如果k大于D,则bk-j seen为0。
使用双层for循环计算每个c_{k}:
第一层for循环计算k从0到n;
内层for循环计算上式中的Σ。
时间复杂度:O(n^2)
利用FFT算法,可以在O(nlogn)时间内完成多项式乘法。
具体做法是:
将a(x)和b(x)使用FFT转化为频域表示A(ω)和B(ω)
乘域A(ω)和B(ω),这只需要O(n)个乘法操作
将乘积信号用IFFT转回时域,即为得到c(x)
总时间复杂度为O(nlogn)
Karatsuba算法使用分治思想,递归地将问题划分为子问题。
对于degree为n的多项式,Karatsuba算法只需要3n^(log_32) ≈ 3n^{1.585} 次乘法。
因此Karatsuba算法的时间复杂度为O(n^{1.585})。比FFT和朴素算法更快。
它利用了a(x)b(x)可以表示为:
a(x)b(x) = z0 + z1x + z2x^2, 其中
z0 = a0b0 z1 = (a1b0 + a0b1) z2 = a1b1
从而只需要3次乘法即可计算乘法结果。
总之,多项式乘法最优算法是Karatsuba算法,其时间复杂度为O(n^{1.585})。
图在计算机科学中是一种重要的数据结构。图可以用来表示许多现实世界中的关系,例如社交网络、交通路网等。
图是由两个集合组成的对:
图可以分为有向图和无向图两种:
计算机科学中常见的两种图表示方法:
图算法的效率是根据图作为算法输入的大小来衡量的:
DFS属于遍历整个图的算法,它会尽可能深地搜索每个节点的后继节点,直到没有任何后继节点后再回溯。DFS通常用于解决以下问题:
图可以表示许多现实世界问题,通过对图问题的研究可以解决诸如社交网络、交通网络等真实问题。因此,系统地学习图算法对理解计算机科学问题和解决实际问题都具有重要意义。
DAG是有向图且没有环路的图。
检测图是否有环路的算法是:
DFS搜索的时间复杂度是O(V+E)
在DFS搜索过程中,为每个顶点维护前序号和后序号:
根据前后序号的区间关系,可以判断边是否是:
在有向图中定义连通性为:从一个节点能通过一条或多条边到达另一个节点。
利用DFS的前后序号,可以检测图是否连通:
时间复杂度为O(V+E)
有向图的连通性与无向图不同,需要检测所有强连通分量而不能仅判断是否每个节点都能互相到达。
上次课我们学习了连通性和路径的概念。图中的最短路径问题是找出从起点到终点的长度最小的路径。
Dijkstra算法解决带权重的最短路径问题。它每次选择距离起点最近的点,将其标记为”已知”,并更新其它点到该点的距离。
算法状态包含两个部分:
distances数组,维护每个点到起点的当前估计距离。随着算法运行,估计距离会逐步趋近于实际 shortest path。
known集合,包含已经“已知” shortest path 的点。对known内每个点,distances数组保存的就是从起点到该点的实际shortest path长度。
最初,known只包含起点,distances数组中起点到自己的距离为0。
算法以下面方式扩展known集合:
从known外部可以直接达到的点中,选择具有最小distances估计值的点a加入known。
更新a周围点到起点的distances估计值。
重复直到所有的点都在known内。此时distances数组记录了各点到起点的实际shortest path距离。
证明known外部可以直接达到的点中,一定存在一个点是其实际shortest path:
考虑从起点到known外某点a的某条shortest path,其必须从known内出发,然后离开known。
由shortest path的定义,路径必须从known边界上的某点出发,该点即为a在known外可直接达到的点。
因此a一定是一个边界点,其实际shortest path即通过一个known内点达到。
若a是known外distances值最小的点,选择它入known必能使得distances更接近实际值。
重复上述过程直至计算出所有点到起点的 shortest path 长度。
Dijkstra算法通过选择known外点集合中的实际最短路径点入集,来逐步求解出所有点到起点的最短路径长度。它正确且高效地解决了带权重的单源最短路径问题。
贪心算法通常是解决最优化问题的一种技巧。相比考虑所有问题的约束,贪心算法采取近视的方案,选择每次都相对最优的局部决策,希望最终能得到一个较优解。
最短路径问题根据不同图的属性可以分成几类:
无向图且边长度均为正值时,使用 Dijkstra 算法。
有向图且不存在负环时,可以使用贝尔曼-福德算法来解,同时也可以检测是否存在负环。
有向无环图(DAG)时,可以利用拓扑排序在线性时间内解决问题。
除此之外,对于有权DAG还可以求解最长路径问题。
贝尔曼-福德算法可以处理任何图,只要问题定义自洽即可。它每一轮迭代都会更新所有边,总迭代次数为V-1次。
可以在贝尔曼-福德算法运行结束后再额外进行一次迭代,如果这一迭代中距离值有更新,则说明存在负环。
对于有向无环图,可以利用其定向性质,以拓扑排序顺序更新边,这样就可以在线性时间内求解最短路径问题,比贝尔曼-福德算法更快。
各种最短路径算法存在内在联系,理解它们在不同图上的应用场景及关系很重要。这对于解决在实际问题中的变化更有帮助。
最小生成树(Minimum Spanning Tree,MST)问题的输入是一张带权图。目标是找出一颗生成树T,使得T包含图中所有的节点,且T的权重和(即所有边的权重之和)最小。
权重可以视为长度或成本,可以是正数或负数,但实际上可以假设都是非负数,因为可以对所有边加上一个足够大的常数不改变结果。
考虑从一个只有节点没有边的图开始,逐步添加边形成一颗生成树。
每添加一条边,都可能使连通图分解成多个连通分量。但任何时刻添加一条正在不同连通分量内两节点的边,都可以使连通分量数量减1。
由于开始节点数量为V,结束时只有1个连通分量。所以总共添加的边数必须刚好是V-1条。
贪心算法,按边权从小到大排序后依次添加边。
加入一条边前检查是否会形成环,不形成即加入答案树中。加入n-1条边后结束。
生成树总边数为V-1。
从空图开始逐步添加边,每次添加都只能使连通分量数量减1。所以总共必需添加V-1条边。
若图含环,可从环中删除一条边不影响连通性。重复此操作直至无环为止。边数将少于V-1,矛盾假设。所以如果边数为V-1,则图必为树,即无环。
Union-Find问题是指要维护一个集合C,C包含1到n之间的不相交子集。Union-Find支持下面三种操作:
使用数组A实现,其中Ai存储元素i所在集合的名称。名称可以是该集合最小元素。
find直接返回Ai。
union(x,y)时,比较Ax和Ay的值,如果不同,则将Ay的值替换为Ax的值。
时间复杂度:find和make-set是O(1),union是O(n)。
使用数组A指向链表节点。每个链表表示一个集合。
find返回节点头元素。
union(x,y)通过遍历将x头节点指向y尾节点,链接两条链表。
时间复杂度:find和union都是O(n)。
在union时,将被合并集合头节点直接指向合并集合头节点,避免链表变长。
如此一来,实际上每个find都会使得节点指向根,所以随着操作越来越多,树的高度会越来越低。
最终平均时间复杂度下降为O(α(n)),α为阶乘函数的反函数。
Union-Find问题是一类常见的数据结构问题,其基本思路是用集合表示节点的连接关系,并支持查询与合并操作。采用优化如路径压缩可以大幅提升性能。
如果X是一棵树的根节点,则X子树的大小至少为2的X节点的秩(rank)次方。
如果沿着父指针向上找到一个节点,则该节点的秩严格大于当前节点的秩。
如果一个节点的秩正好为K,则拥有秩K的节点数量最多为N/2^K。换句话说,没有节点的秩可以大于log_2N。
如果进行:
则总时间复杂度为O(M + Nlog*N)
将秩分组。秩从0到1作为一组,1到2^1作为一组,2^1到2^2作为一组,依此类推。
当一个节点的秩升到K时,向它“开标签”,deposit 2^K金额。
秩可能继续升高,当升到下一组时,再deposit更多金额。
所有开标签总金额和为O(Nlog*N)
每做一次操作,即使1个时间步长
有时会将时间步长记入某个节点的“标签”上
最后统计直接计数的时间步长和,加上每个节点标签余额,即为总时间步长
可以证明标签金额总和小,且没有标签会转负,因此可以通过此方法计时
总时间步骤为O(M + Nlog*N)
给出有向无环图G和结点s和t,找出从s到t的最短路径长度。
算法使用动态规划,定义函数f(t)表示从s到t的最短路径长度。f(t)满足如下递归关系:
为了实现这个递归,需要使用记忆化搜索。维护两个表:
算法复杂度为O(V+E)
不仅返回最短路径长度,还需要返回具体路径。
修改choices表保存每个结点t的最优前驱结点q,然后从t往回推到s,就可以恢复出完整路径。
如果f(t)=infinite则返回无路径,否则逐步追踪choices表里记录的前驱结点,就可以得到从s到t的完整最短路径。
札记提供实现最短路径算法的Python代码,该代码将公开提供在课程网站上,供学习者下载执行。这可以帮助学习者更好地理解和练习算法。
讲课将使用黑板进行方程和例子的讲解,同时也会实时代码来帮助学习理解算法思想和实现过程。如果读不清楚代码,可以抬手提问调整字体大小。
除此之外,也欢迎学习者在课后提出其他问题。
给定一系列矩阵需要乘积,不同的括号化方式将导致不同的时间复杂度。目标是找到括号化的最优顺序,使得总时间复杂度最小。
对于矩阵A、B、C,它们的乘法顺序可以有(AB)C或者A(BC)两种,对应的时间复杂度也不同。
假设矩阵A是m×n矩阵,B是n×p矩阵,则:
总时间复杂度为顺序决定。
给定矩阵序列A1,A2,…,An,其中Ai是si×si+1矩阵
定义函数F(i,j)为从Ai到Aj这一范围内矩阵乘法的最优时间复杂度
F(i,j) = min(F(i,k)+F(k+1,j)+si×sk+1×sj+1),其中i≤k<j
若i=j,则F(i,j)=0,因为只有一个矩阵直接返回
该动态规划算法的时间复杂度是O(n^3),空间复杂度是O(n^2)。
教师表示下一主题将进入线性规划问题。
线性规划可以通过两个格式表示:
格式α: max C^T X, 使得aX ≤ B, X≥0 格式β: max C^T X, 使得AX = B, X≥0
这两个格式是等价的。可以通过增加少量变量和约束来转换表示。
对偶性理论提出,原始问题的最优值不大于对偶问题的最优值。如果原始问题无界,则对偶问题是不可行的。如果对偶问题无界,则原始问题是不可行的。
网络流问题是线性规划的一个特例。它描述一个有向图中水流通过管道的情况。
网络包含源点s和汇点t,其他点为结点。管道代表有向边,每个管道有容量限制。
源点s有无限量水供给,汇点t可以接收无限量水。其他点水量保持平衡,流入等于流出。
目标是找到从s到t的最大流量。流量必须满足每个管道的容量限制。
可以使用增广路算法找出网络最大流:
证明该算法能找到网络最大流,并给出时间复杂度。
本节课将证明最大流最小割定理:最大流的值等于源点到汇点的最小割容量。
清杆图(残差图):对于一条有容量限制的边e,如果其流量f(e)达到容量c(e),则在残差图中删除该边;否则,其残差容量为c(e)-f(e),且边方向反转。
流分解定理:任何有效流都可以分解为若干条不包含循环的路径流。
残差图仍然符合流网络的要求。
任何有效流F都可以分解成不包含交叉的路径流和不包含交叉的循环流之和。
对任何残差图G′和有效流F′,F′都是G′的有效流。
源点s到汇点t的截面:将所有顶点切分成包含s的一边和包含t的一边。
割面的容量:从包含s一边到包含t一边的边的总容量和。
段流:通过某一截面流入和流出的净流量。
说明任意流F和任意截面,该截面段流等于流F的值。
由此可知,最大流的值等于最小截面段流,即最小截面容量。
使用数学归纳法证明第一个命题。
最大流值等于源点到汇点的最小割容量。
最大流问题可以用线性规划来表示,对应的对偶问题就是最小割问题。最大流最小割定理实际上是一个原问题和对偶问题的等价定理。
最大流算法可以应用到网络流分配、图中的分割问题等多种场景。
零和博弈是一种博弈理论中的概念。它指的是当一个玩家在博弈中获得的利益等于另一个玩家损失的利益时,两玩家的利益和为零。
以老鹰捉兔子为例:
这样一来,无论结果是什么,老鹰和兔子的利益总和总是为零。
可以用一个 payoff 矩阵来描述石头剪刀布游戏:
例如,如果A玩石头B玩剪刀,A获胜得1分,B输掉1分,记录为矩阵元素为1。
在博弈中,玩家可以采取:
以石头剪刀布为例,随机选择就是一个混合策略。
用来衡量某种策略的好坏。计算公式为:
期望收益 = ΣiΣj P(策略i)P(策略j) * 收益矩阵元素
其中:
在石头剪刀布游戏中,随机策略的期望收益不论对方采用什么策略,都为0。这意味着随机策略是一种稳定的策略。
该问题涉及多个专家的日常预测,比如天气预测。
为了给出一个相对的保证,我们采用“悔中”这个标准:
这种策略很懒惰。如果第一个专家每天都损失很大,而最后一个专家每天都没有损失,那么这种策略的悔中就可能很大。
为了更好地评估策略,我们需要考虑损失的值可以“共谋”让策略效果很差。例如,第一个专家每天都应当有很大损失。
此外,我们假设所有损失都限制在0-1范围内。
本节介绍了专家问题的基本设置和一个简单的策略,并讨论了如何更好地评估策略以避免过于乐观。
本次课将介绍最大匹配问题。最大匹配问题是在二分图中找到一个匹配集,其中边的数量最多,且任意两个边不能共用一个顶点。
二分图是一个图,其顶点集可以分为左集合和右集合,边只可以连接左右两边的顶点。最大匹配问题的目标是找到二分图中的一个匹配集,使该匹配集中的边的数量最大化。
最大匹配问题常见的应用场景包括:任务分配问题(左集合为任务,右集合为处理器)和配对问题(左集合和右集合为不同类型的实体)等。
最大匹配问题可以通过求解最大流问题来解决。具体做法如下:
将原始二分图转换为有向图网络。新增源点s和汇点t,用有向边将s连通左集合,将右集合连通t。原二分图边改为有向边。
所有新增边和原始二分图边的容量均设为1。
求得该网络中的最大流。
若最大流中的某条边的流量为1,则该边在原二分图中就是匹配集中的一条边。
原因在于:最大流网络中容量为1的边,流只能通过这条边流转,否则会违反流量守恒定律。而最大流的值等于匹配集中的边数。
最后,由于求最大流问题的算法(如福特算法)得到的流量一定是整数流,所以匹配集也一定存在。
最大匹配问题通过求解最大流问题被很好解决了。这也揭示了问题之间可能存在的等价关系,就是归约。
二项关系是一个字符串对的集合。实例(X)和见证(W)就是字符串对。
关系R定义了两个计算问题:
决定问题(Decide R):给一个实例X,输出是否存在见证W使得(X,W)在R中。
搜索问题(Search R):给一个实例X,找到一个见证W使得(X,W)在R中,如果不存在输出fail。
如果能解决搜索问题,也能解决决定问题。但反过不一定。
语言L对应的一个关系R,是所有实例X中存在见证W使(X,W)在R中的集合。
不是所有的关系的决定问题都能高效解决。如停机问题就没有算法能解决。
所以我们只讨论“可计算关系”R。它有一个验证器V_R,能在多项式时间内判定(X,W)是否在R中。
如果R是可计算关系,那么决定问题可以在2^Poly(x)时间内解决。
P类是那些决定问题都可以在多项式时间内解决的关系集合。
NP类是那些搜索问题都可以在多项式时间内解决的关系集合。
许多问题看起来难以解决,但通过将它们归为已知问题的函数,就可以利用已知问题的算法解决它们。这就是归约的概念。
今天我们会用归约的概念来研究交互性问题。先定义关系和语言,然后引入可计算关系的概念。进而定义P类和NP类,以便用它们来描述交互性难题。
上次我们定义了P类和NP类,以定义这些复杂度类必须提出问题的抽象概念——有效可计算的二值关系。P类包含可以在多项式时间内解决的决定问题。NP类包含可以在多项式时间内验证解的决定问题。
我们引入了NP难和NP完备的概念。NP难意味着所有NP问题都可以归约到它。如果一个问题同时满足NP难和在NP内,那么该问题就是NP完备的。
我们给出了第一个NP完备问题——布尔可满足性问题(SAT)。我们证明了它的特殊情况——3SAT也是NP完备的。
3SAT问题几乎和SAT问题一致,但我们限定公式必须是3-CNF形式。即公式是一个连续或(OR)的结合,每个连续或包含三个子句。
子句是变量或其否定形式。例如:
X1 ∨ X2 ∨ ¬X3
我们将证明3SAT仍然是NP完备的,尽管它比原始SAT问题更具结构性。
给出3-CNF公式Φ和候选替代量v,我们可以在多项式时间内验证v是否满足Φ。
另外,3SAT是SAT的特例,而SAT本身就属于NP。所以3SAT也属于NP。
我们将展示SAT可以归约到3SAT。设给一个布尔公式Φ,我们将Φ变换成3-CNF公式Φ’,使得:
这个变换分两步:
通过这个归约,我们证明了只要有一个可以解3SAT的算法,就可以解任何SAT问题。所以3SAT是NP难的。
daher,3SAT同时满足NP难和在NP内,所以3SAT是NP完备的。
上次我们使用NP归约来证明独立集问题与哈密顿回路问题属于NP完整问题。也就是如果能高效解决这两个问题,就能高效解决满足性问题,而满足性问题已经被证明是NP完整的。
当一个问题被证明是NP完整后,我们通常会采取以下方法:
尝试改变问题定义,寻找某个特定条件下的问题不属于NP完整。
来写一个正确但效率低下的算法,例如时间复杂度为指数级的算法。然后探索优化算法以减缓指数级效率下降。
来写一个高效但不一定正确的近似算法。要求算法必须在多项式时间内完成,同时给出近似度保证,即算法找到的解从最优解起不超过某个倍数。
使用启发式算法,无法给出运行时间或近似度保证,但在实践中效果不错。
今天主要介绍近似算法。近似算法要求运行在多项式时间,同时给出近似度保证α。即算法找到的解最坏情况下离最优解不会超过α倍。这种算法使得原本NP完整问题在实际可应用。
举个例子,最大决策森林划分问题可以用二分近似算法解决。该算法时间复杂度为O(nlogn),且找到的解一定不会比最优解差超过一倍。这种α=2的近似算法显著减轻了问题的困难度。
近似算法是计算机科学中的重要研究方向。人们关注不同NP问题的近似度下限,探索各问题最佳近似比例的算法。近似度会因问题而异,是衡量算法质量的重要标准。
本节授课将讨论随机算法。随机算法并不是输入数据本身是随机的,而是算法在运行过程中会自己作出随机决定。我们仍然采用最坏情况时间复杂度来分析算法,但是算法本身含有随机元素。
随机算法主要有两种:
拉斯维加斯算法。此类算法结果总是正确的,但是其运行时间是一个随机变量。我们希望显示运行时间在期望值或高概率下能够保持较小。
蒙特卡罗算法。此类算法运行时间具有确定的上限,如N平方时间或NlogN时间等,但是正确性结果是个随机变量。我们希望给出输入的数据集,使用随机字符串后算法产生正确结果的概率能够控制在较高水平,如90%以上。
快速排序是一种拉斯维加斯算法。它的工作原理是:
理想情况下,基准元素选择在数组中间位置,这样可以使得左右两部分规模相等,递归关系是T(n)=2T(n/2)+O(n),时间复杂度为O(nlogn)。
但是如果基准元素偏差很大,如 siempre选择最小/最大元素,那么时间复杂度可能恶化到O(n^2)。
快速排序的平均时间复杂度也为O(nlogn)。
理由如下:
时间复杂度与比较次数成正比。
每次比较都等概率选择基准元素,期望划分数组规模比例为1:1。
用马尔可夫不等式概括期望比较次数为O(nlogn)。
所以快速排序的平均时间复杂度为O(nlogn)。它总能保证正确结果,但是单次运行时间是随机变量。
随机算法还包括算法,例如:
抽样调查:快速求解但结果可能错误,错误率可以控制在很低水平。
蒙特卡罗方法解积分:时间复杂度确定,但求解结果误差可控。
总体来说,随机算法能以较低平均复杂度求解一些问题,触发高效机会,但也面临最大复杂度故障隐患。它们在实践中广泛应用。
流式算法指的是在数据流不断输入的情况下,能够进行计算并回答查询的一类算法。其特点是:
问题描述:需要维护一个计数器B,支持以下3种操作:
直接使用计数器的算法需要O(logN)的内存。如果允许近似解,即使用alpha倍误差范围内返回结果,则可以用O(loglogN)的内存实现。
具体思路是:将可能的计数值√1,√α,√α^2,…√α^log^αN映射成1,2,…log^αN的指数值返回。这样不同的计数值间隔足够大,就可以用较少内存状态区分。
莫里斯算法用于近似计数问题,只使用一个变量X来指示计数区间。具体算法:
其原理是:变量X的期望值正好等于实际增量操作次数。因此返回2^X-1的值就是计数范围内的一个近似值。
这个算法只使用O(loglogN)内存,即可以高效地实现流式算法近似计数这类问题。
在本课中,我们主要研究计算问题的下界。计算下界意味着证明问题的复杂度不可能低于某个值。
我们已经看到排序问题在比较模型下的下界是Ω(nlogn)。
NP完全问题如3satisfiability问题如果难解,那么其他NP难问题也都难解。但是,我们并不知道P是否等于NP,这是一个开放问题。所以NP完全性结果依赖一个“如果”条件,不能作为绝对的下界结果。
我们能在一些具体模型下得到下界结果。比如布尔电路复杂度模型,可以将计算问题映射成一系列Boolean函数,然后研究对应函数的电路规模下界。人们已知电路规模不可能低于2^Θ(s)对应的函数规模。
我们能明确证明时间下界的问题是某种时间层次问题。给定函数实现C和输入X,判断C在n^3次步内是否返回true。这个问题的任何正确算法时间下界是Ω(n^(2.999)).
总的来说,除去一些特殊模型,我们对许多常见问题的下界了解还很有限。我们当前无法证明像3satisfiability这样的NP难问题无法在多项式时间内解决。证明问题下界仍然是一个开放和困难的研究课题。
给出一组键值对(key-value pairs),构建一个数据结构来支持键的搜索查询。
搜索查询的定义:传入数据结构和关键字,如果关键字是原始键值对中的一个键,返回这个键对应的value;否则返回特殊符号表示没有查找到。
设计数据结构时要考虑:
将键值对排序后构建数据结构。
数据结构大小:n 搜索时间:O(logn) 二分搜索
构建一个包含所有可能键的庞大数组,用键值作为索引直接查询。
数据结构大小:键的可能空间(通常远大于n) 搜索时间:O(1)
使用哈希函数将小量键(n个)映射到较小的地址空间(大小m)。
期望:哈希函数使得大部分键都很少冲突。
这样可以使数据结构大小接近n,搜索时间接近O(1)。
取键的某部分比特作为槽地址 - 问题:同一组键的相同前缀可能都映射到同一槽
使用混合函数,如:
这类函数可以使哈希值的分布更均匀随机
NP类可以被视为标准证明的形式化。标准证明指利用已有公理和推理规则,通过有效的推理过程来验证定理是否成立。
我们可以把实例x视为一个定理,证明pi视为验证该定理是否成立需要的证明。对于x属于语言L的定理,存在证明pi可以使验证器v接受;对于x不属于L的假定理,不存在任何证明可以使验证器v接受。
交互证明提出让验证器v与证明者p进行对话交互,p根据对话情况动态提供信息。如果验证器v是随机算法,交互证明的概念就与NP类不同了。
对于语言L中每一个实例x,存在证明者p,通过与验证器v的对话可以使v输出1的概率为1。
对于不在语言L中的每个实例x,无论采用哪个证明者p,通过与验证器v的对话可以使v输出0的概率至少为1/2。
完整性和声量性对应于NP类中的完整性和声量性,它们分别保证了正确定理可以被证明,错误定理不能被证明。
将验证器v和证明者p同时视为交互图灵机,定出它们交互的规则。如果交互后v输出1的概率满足完整性,输出0的概率满足声量性,则这个语言属于IP类。
IP类扩展了NP类,考虑了证明的交互性,而不再限于非交互性证明。它是理论计算机科学一个重要的概念。