算法基础-02.NP问题简介

上一节学习了时间复杂度的计算,问题按照时间复杂度可以分为以下问题:

  1. O(p^n):不可以解决,复杂度太高,那么怎么解决这类问题?
    1.1 对于小型的问题仍然采用此复杂度的算法;
    1.2 提出一个近似算法进行优化,变为简单问题。
  2. O(n^p): 这个问题用计算机可以解决。

典型的O(p^n) 问题有哪些?

Multi-objective shortest path problem
“你有一个交际网,每个人是一个节点,认识的人之间相连。你要通过一个最快、最省钱、最能提升你个人形象、最没有威胁、最不影响你日常生活的方式认识一个萌妹,NP-hard”

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容