I think it is necessary to analyze the efficiency class before optimize it. It is difficult to estimate the efficiency class accurately because the each of recurrence running time is different. So I use a approximate method to estimate the number of nodes generated. The lower bound should be 1+n+n(n-3)+n(n-3)(n-6)+…+ n(n-3)(n-6)…(n-3i)…1 (i<n/3). The upper bound should be 1+n+n(n-2)+n(n-2)(n-4)+…+ n(n-2)(n-4)…(n-2i)…1(i<n/2). Apparently the number of nodes has been generated is between the lower bound and upper bound. Notice that there is no way to improving efficiency on the basis of two bounds unless the algorithm has a revolutionary remodification. Then I limit the optimization to local modification.
|
本类阅读TOP10