← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 9842.e · 生成模型:Hunyuan

计算复杂性与NP问题

理解等级:高级

衡量算法看时间复杂度与空间复杂度,占用资源越多说明问题本身越复杂。能否在多项式时间求解划出了易解与难解的分界:多项式时间算法对应易解问题,指数时间算法对应难解问题,后者随规模增长耗时暴涨,虽有算法却不适用大规模场景;把指数算法改造成多项式算法,正引出著名的P=NP问题。按状态转移的确定性再分类:P类问题能用多项式时间的确定性算法求解,每步状态唯一、结果唯一;NP类问题用多项式时间的非确定性算法求解;NP完全问题是NP中最难的子类,至今没有找到多项式算法。背包、最短路径、旅行商、最大团、图同构都是典型的NP类问题。机器学习的多数算法正面向NP类,其结果落在允许误差范围内。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第5章 梯度寻优 · 查看原书依据

      而NP类问题是指可以用多项式时间的非确定性算法来进行判定或求解,也就是说,对这类问题求解的算法大多是非确定性的,但时间复杂度有可能是多项式级别的。

    参考来源

    - 位置:《机器学习算法原理与编程实践》第5章 梯度寻优(源文件:extracted/机器学习算法原理与编程实践/_epub-src/OEBPS/text00019.html) - 结论依据:原文定义时间与空间复杂度,用多项式/指数时间区分易解与难解,并给出P、NP、NP完全的界定与典型NP问题例子。 - 原始内容:而NP类问题是指可以用多项式时间的非确定性算法来进行判定或求解,也就是说,对这类问题求解的算法大多是非确定性的,但时间复杂度有可能是多项式级别的。