Sunday算法效率分析

Study on efficiency of Sunday algorithm

针对Sunday算法的过程比较复杂,难以构建马尔可夫链的问题,提出一种新的根据算法的匹配次数差求平均效率的方法。首先选定初等算法作为效率分析的基准算法,使用马尔可夫链得出初等算法比较精确的平均效率估计公式;然后根据相应的概率公式计算出初等算法和Sunday算法匹配过程的差值;将两者结合,得出Sunday算法平均效率估计公式。实验结果表明,由此公式计算的估计值可以代表实际匹配次数的平均值。

Given the characteristic that the Sunday algorithm is too complex to construct Markov chains,a new method according to the difference of matching number in the algorithms was proposed to compute the average efficiency.Firstly,the naive algorithm was chosen as the foundation,and its accurate average efficiency was computed by Markov chains.Secondly,the difference of the two algorithms was computed by the corresponding knowledge in probability theory.The two results were combined to get the equation which represented the average efficiency of Sunday algorithm.The experimental results show that the estimated value computed by the equation is the average number of the matching times.