[算法设计与分析-从入门到入土] 复杂算法

[算法设计与分析-从入门到入土] 复杂算法

个人导航

知乎：https://www.zhihu.com/people/byzh_rc

CSDN：https://blog.csdn.net/qq_54636039

注：本文仅对所述内容做了框架性引导，具体细节可查询其余相关资料or源码

参考文章：各方资料

复杂算法

时间复杂度层级:
O ( 1 ) < O ( log ⁡ n ) < O ( n ) < O ( n log ⁡ n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
多项式时间(polynomid time):
O ( 1 ) , O ( log ⁡ n ) , O ( n ) , O ( n log ⁡ n ) , O ( n 2 ) , O ( n 3 ) O(1),O(\log n),O(n),O(n\log n),O(n^2),O(n^3)O(1),O(logn),O(n),O(nlogn),O(n2),O(n3)

• P问题（Polynomial Problem）：能在「多项式时间内直接解决」的问题
  (比如数组遍历、简单排序)
• NP问题（Nondeterministic Polynomial Problem）：无法保证在多项式时间内解决，但能在「多项式时间内验证一个候选解的正确性」的问题
  (比如“旅行商问题的某个路径是否符合要求”)

千禧难题: P vs NP
能在多项式时间内验证解的问题（NP），是否必然能在多项式时间内解决（即 P = NP）？

1. 主流观点：多数科学家相信P ≠ NP（即存在多项式时间可验证但无法多项式时间解决的问题），但目前尚未有严格证明
2. 重要影响：若P = NP被证明，现行多数加密体系（如RSA加密）将彻底失效——因为这些加密的核心依赖“大整数分解无法在多项式时间内完成”，一旦该问题可多项式时间解决，加密信息可被快速破解

NP完全问题（NP-complete, NPC）：

• 自身是NP问题
• 所有其他NP问题都能在多项式时间内“归约”到它

NP难问题（NP-hard）：

• 自身不一定是NP问题(可能无法在多项式时间内验证解)
• 所有其他NP问题都能在多项式时间内“归约”到它

难度: NP难问题 ≥ NP完全问题

应对复杂问题

• 回溯法(Backtracking) /分支界限法(Branch and Bound)
  -> 正确解
• 随机算法(Randomized Algorithms)
  -> 有可能得到的是近似解
• 近似算法(Approximation Algorithms)
  -> 近似解

精确度越来越低, 求解速度越来越快