数据结构中的替代方法
在这里,我们将看到如何使用替代方法来解决递归关系。我们将举两个例子来更好地理解它。
假设我们正在使用二进制搜索技术。在这种技术中,我们检查元素是否存在于末尾。如果在中间存在,则算法终止,否则我们一次又一次地从实际数组中获取左右子数组。因此,在每一步中,数组的大小都会减小n/2。假设二进制搜索算法需要T(n)的时间来执行。基本条件需要O(1)的时间量。所以递归方程将如下-
$$T(n)=\开始{cases}T(1)&for\:n\leq1\\2T(\frac{n}{2})+c&for\:n>1\end{cases}$$
解决-我们将在每个步骤中替换公式以得到结果-
$$T(n)=T(\frac{n}{2})+c$$
通过代入T(N/2),我们可以写成
$$T(n)=(T(\frac{n}{4})+c)+c$$
$$T(n)=T(\frac{n}{4})+2c$$
$$T(n)=T(\frac{n}{8})+3c$$
$$T(n)=T(\frac{n}{2^{k}})+kc$$
现在,如果$$(\frac{n}{2^{k}})$$达到1,则表示2k为n。所以k的值是log2