文件名称：Viterbi算法的复杂度-隐马尔可夫模型及其在自然语言处理中的应用
文件大小：642KB
文件格式：PPT
更新时间：2024-05-14 08:52:42
隐马尔可夫 自然语言处理
Viterbi算法的复杂度 假定有N个词性标记（罐子），给定词串中有M个词（彩球） 考虑最坏的情况，扫描到每一个词时，从前一个词的各个词性 标记（N个）到当前词的各个词性标记（N个），有N×N=N2 条路经，即N2次运算，扫描完整个词串（长度为M），计算 次数为M个N2相加，即 对于确定的词性标注系统而言，N是确定的，因此，随着M长 度的增加，计算时间以线性方式增长。也就是说，Viterbi 算法的计算复杂性是线性的。 N2×M。