关键词: Sunday算法, 算法效率, 马尔可夫链, 初等算法, 平均匹配次数

Abstract: 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.

Key words: Sunday algorithm, algorithm efficiency, Markov chain, naive algorithm, average matching number