下面分析它的时间复杂度,设串s长度为n,串t长度为m。 匹配成功的情况下,考虑两种极端情况: 在最好情况下,每趟不成功的匹配都发生在第一对字符比 较时: 例如: aaaaaaaaaabc 设匹配成功发生在s处,则字符比较次数在前面i-1趟匹配 中共比较了i-1次,第道趟成功的匹配共比较了m次,所以总共 比较了-1+m次,所有匹配成功的可能共有nmn+1种,设从s 开始与t串匹配成功的概率为p,等概率情况下p=1/(n-m+1), 因此最好情况下平均比较的次数是: N一+1 ∑m×0-1+m)2-1+m +m 即最好情况下的时间复杂度是O(n+m)。 2021年1月21日 数据结构讲义 192021年1月21日 数据结构讲义 19 • 下面分析它的时间复杂度，设串s长度为n，串t长度为m。 匹配成功的情况下，考虑两种极端情况： 在最好情况下，每趟不成功的匹配都发生在第一对字符比 较时： 例如：s=”aaaaaaaaaabc” ，t=”bc” 设匹配成功发生在si处，则字符比较次数在前面i-1趟匹配 中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共 比较了i-1+m次，所有匹配成功的可能共有n-m+1种，设从si 开始与t串匹配成功的概率为pi，等概率情况下pi=1/(n-m+1)， 因此最好情况下平均比较的次数是： 即最好情况下的时间复杂度是O(n+m)