为求得前向变量αt(i,d),首先需要计算求和式:for∀i,计算量为O(N2)步,然后对于∀i,d,求αt(i,d)需要计算O(N.D)步,因此对于每一时刻t,计算前向变量共需要O(ND＋N2)步。
同样对于后向变量,对于∀j,计算需要O(ND)步,对于∀i,计算βt(i,1)需要O(N2)步,因此计算在时间t时的βt(i,d)一次其需要O(ND＋N2)步。
所以对于一长度为T的观察序列期计算时间为O((ND＋N2)T)。
for∀i,计算量为O(N2)步,然后对于∀i,d,求αt(i,d)需要计算O(N.D)步,因此对于每一时刻t,计算前向变量共需要O(ND＋N2)步。
需要O(ND)步,对于∀i,计算βt(i,1)需要O(N2)步,因此计算在时间t时的βt(i,d)一次其需要O(ND＋N2)步。