算法复杂性分界函数—多项式
2021-05-19 12:29
标签：问题： strong 转换 特定 为什么 提高 算法 回溯法 计算机系统 以多项式作为分界函数？ 一、常见算法大致分为两类： 一类是多项式时间内可实现的 另一类需要指数时间（O(cn)） 二、多项式时间算法与计算模型无关 算法的研究依赖于计算模型。在不同类型计算模型上实现算法，计算时间不同。 广义Church-Turing命题：不同计算模型上的计算时间有多项式时间关系。 多项式与多项式的复合函数是多项式，因此，多项式算法与计算模型无关。 问题分类 一、判定问题 解只有两种，yes或no 例：给定图G=(V,E)，问该图是否有哈密尔顿圈。 二、优化问题 例：给定图G=(V,E)，假设边的费用为自然数。求改图的最短哈密尔顿回路。 三、问题转换 优化问题可转换为相应的判定问题求解。 是否所有的难解问题通过并行计算使其在多项式内可解？ 关于并行算法：当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行的操作，从而大大地限制了并行计算机系统的加速能力。 阿达尔定律：串行执行操作仅占全部操作1%，解题速度最多只能提高一百倍。 阿达尔定律告诉我们，对于有些难解问题，即使提高计算机运行速度，也不能在多项式时间内验证。即并非所有的难解问题都属于NP类。如，汉诺塔问题：推测阶段给出一种盘子移动方法；验证阶段需要2n步验证该解的正确性。 P类和NP类问题的差别 主要差别在于： P类问题可以用多项式时间的确定性算法进行判定或求解。 NP类问题可以用多项式时间的确定性算法来验证它的解。 结论： P?NP 猜测： NP≠P？ 解决NP=P？的途径 解决这个猜想，有两种可能： 一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个多项式算法，即可证明NP=P。 另一种可能，就是这样的算法是不存在的。需要从数学理论上证明它为什么不存在。 NP完全问题的近似解法 算法复杂性分界函数—多项式 标签：问题： strong 转换 特定 为什么 提高 算法 回溯法 计算机系统 原文地址：https://www.cnblogs.com/zhangzefei/p/9742472.html
上一篇：图灵机与确定性算法
下一篇：池模块 -进程池 -线程池