参数化复杂性：计算复杂性理论中的一个分支，用“参数”（如解的大小、树宽、图的度数等）来刻画问题难度。它关注：即使一个问题整体上很难（例如 NP-困难），当某个参数较小时，是否仍能设计高效算法（典型形式如运行时间为 (f(k)\cdot n^{O(1)}) 的算法）。
/pəˈræmɪtəˌraɪzd kəmˈplɛksɪti/
Parameterized complexity is useful for studying NP-hard problems.
参数化复杂性对于研究 NP-困难问题很有用。
In parameterized complexity, an algorithm can be efficient when the chosen parameter is small, even if the overall input size is large.
在参数化复杂性中，即使整体输入规模很大，只要选定的参数很小，算法也可能依然高效。
“Parameterized”源自 parameter（参数），表示“用参数来描述/控制”；“complexity”表示“复杂性”。合起来指“用参数来刻画与分析计算问题复杂性的理论框架”。该术语在20世纪末随着固定参数可解（FPT）等概念的发展而广泛使用。
Select Language