数据结构中的递归方程
在分析算法时，我们发现了一些递归关系。这些递归关系基本上在表达式中使用相同的函数。在大多数情况下，进行递归算法分析以及分治法，我们可以获得递归关系。
在这里，借助一些示例，我们将看到一个递归方程的示例。假设我们正在使用二进制搜索技术。在这种技术中，我们检查元素是否存在于末尾。如果在中间存在，则算法终止，否则我们一次又一次地从实际数组中获取左右子数组。因此，在每一步中，数组的大小都会减小n /2。假设二进制搜索算法需要T(n)的时间来执行。基本条件需要O(1)的时间量。所以递归方程将如下所示-
$$T(n)= \开始{cases} T(1)＆for \：n \ leq 1 \\ T（| \ frac {n} {2} \ rvert）+ c＆for \：n> 1 \结束{cases} $$
同样，如果选择另一个示例，例如合并排序，那么在这种情况下，我们会将列表分为两部分。这种划分一直进行到列表大小仅为1为止。之后，我们按排序顺序将它们合并。合并算法需要O(n)的时间。因此，如果合并排序算法花费的时间为T(n)，则将其分为两个部分，并对每个部分执行相同的任务，则它们将花费T（n / 2），依此类推。所以递归关系将如下所示-
$$T(n)= \开始{cases} T(1)＆for \：n = 1 \\ 2T（\ frac {n} {2}）+ cn＆for \：n> 1 \ end {cases} $$
我们可以使用不同的方法（例如替换，递归树方法）来求解这些方程式，并且可以使用Master方法来求解某些特殊类型的递归关系。
以上是 数据结构中的递归方程 的全部内容， 来源链接： utcz.com/z/321570.html
