势函数:对 $i=[1,n]$ 自定义 $f(i)$,使得每一步势能变化期望 +1/-1,通过求初态与终态的势能差求期望步数
注意:这里的 $f(i)$ 是可以自拟的,即只要满足每一步势能变化期望为 +1/-1 即可!
所以说,这本质上是通过人类智慧定义这么一个函数!
常见形式:$\sum\limits_{i=1}^{n}f(a_i)=1+\sum\limits_{i=1}^{n}(uf(a_i)+vf(a_i+1)+wf(a_i-1))$
此时就可以把外面的 $1$ 变成 $\sum\limits_{i=1}^{n}a_i$ 或者 $\sum\limits_{i=1}^{n}\frac{1}{n}$ 代到右边去,然后拆掉 $\sum$,变成:
$f(a_i)=a_i+uf(a_i)+vf(a_i+1)+wf(a_i-1)$
然后递推构造 $f(x)$ 即可!
注意只有 $f(0)$ 可以随意地拟为 0(其他值可能也不一定行),$f(1)$ 则必须由 $f(0)$ 递推一次出来!(可以假设 $f(-1)=0$ 之类的)