CYK算法 编辑
CYK算法是由约翰·科克，Younger和嵩忠雄共同研究出来大约发表于1965年的一个算法，它是一个用来判定任意给定的字符串



 
w
∈

Σ

∗




{\displaystyle ~w\in \Sigma ^{*}}

是否属于一个上下文无关文法的算法。普通的回溯法在最坏的情况下需要指数时间才能解决这样的问题，而CYK算法只需要多项式时间就够了。CYK算法采用了动态规划的思想。
1
相关
约翰·科克，又译为约翰·考克、约翰·寇克，生于美国北卡罗来纳州夏洛特，计算机科学家，在电脑架构及编译器最佳化技术方面有重大贡献，因此获得图灵奖。曾提出CYK算法。在他主导的IBM 801计划中，首次采用RISC架构，因此被称为RISC架构之父。