吉林大学算法设计与分析考前突击

这篇具有很好参考价值的文章主要介绍了吉林大学算法设计与分析考前突击。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

简答题（25分）

以比较为基础的检索算法的时间下界是O(logn);
以比较为基础的分类算法的时间下界是O(nlogn);
简要说明理由：
NP完全问题一定是NP难问题，但NP难问题不一定是NP完全问题；
算法的五大特性：确定性，能行性，输入，输出，有穷性。
而计算过程只满足前4条特性，不满足“有穷性”；
最优性原理：
无论过程的初始状态或者初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
最优性原理成立的例子：流水线调度问题，货郎担问题；
最优性原理不成立的例子：多段图问题（以乘法作为路径长度且出现负权边时或包含负长度环的任意两点间最短路径问题；
P：所有可在多项式时间内由确定算法求解的判定问题的集合；
NP:所有可在多项式时间内由不确定算法验证的判定问题的集合；
COOK定理：可满足性在P内，当且仅当P=NP;
NP-难度：如果可满足性约化为一个问题L，则称此问题L是NP-难度的。
NP-完全：如果L是NP难度的而且L属于NP，则称问题L是NP完全的。
可满足性问题：对于变量的任一一组真值指派确定公式是否为真。
贪心方法不一定能得到01背包问题的最优解。
例如：
分支限界算法中c帽(x)是c(x)的下界；
问题状态：树中每一个节点确定所求解问题的一个问题状态；
状态空间：由根节点到其他节点的所有路径确定了这个问题的状态空间；
解状态：解状态是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组；
答案状态：答案状态是这样一些解状态S，对于这些解状态，由根到S的那条路径确定了这问题的一个解。
解空间的树结构即为状态空间树；
分治法的三个基本步骤：
分：将n个输入分成k个不同的可独立求解的子问题；
治：求出这些问题的解；
合：通过适当的方法将每个问题的解合并成整个问题的解。