[算法设计与分析-从入门到入土] 复杂算法
个人导航
知乎：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）？
- 主流观点：多数科学家相信P ≠ NP（即存在多项式时间可验证但无法多项式时间解决的问题），但目前尚未有严格证明
- 重要影响：若P = NP被证明，现行多数加密体系（如RSA加密）将彻底失效——因为这些加密的核心依赖“大整数分解无法在多项式时间内完成”，一旦该问题可多项式时间解决，加密信息可被快速破解
NP完全问题（NP-complete, NPC）：
- 自身是NP问题
- 所有其他NP问题都能在多项式时间内“归约”到它
NP难问题（NP-hard）：
- 自身不一定是NP问题(可能无法在多项式时间内验证解)
- 所有其他NP问题都能在多项式时间内“归约”到它
难度: NP难问题 ≥ NP完全问题
应对复杂问题
- 回溯法(Backtracking) /分支界限法(Branch and Bound)
-> 正确解 - 随机算法(Randomized Algorithms)
-> 有可能得到的是近似解 - 近似算法(Approximation Algorithms)
-> 近似解
精确度越来越低, 求解速度越来越快
