在主定理中找到 f(n) 的值

Question

首先声明一下，我知道主定理的性质，所以问题不在这里。

我需要知道如何使用现有算法确定主定理的值

所以，我需要有 T(n)=a*T(n/b) + f(n).

我知道a是递归调用的次数。

我知道b是问题的除法大小

但是不知道f(n)是什么

我有一个例子；

这里我们有 a=2; b=2 f(n) = n

a=2 因为我们有2次merge函数调用 b=2 因为 j=(k+i)/2

但我不明白我们如何得到 f(n)=n

mergeSort(T,i,k)

需要T数组

i,k 整数使得 Tm<=i<=k<=TM 其中 Tm 和 TM 是 T

的边界

确保 T 在 i 和 k 之间排序

`if (k>i) then
    j=(k+i)/2;
    mergeSort(T,i,j);
    mergeSort(T,j+1,k);
    append(T,i,j,k);`

感谢您的帮助。

Answer 1

在主定理中，f(n)是给出运行时递归定义的非递归部分的函数。在递归调用的每一步，算法都会调用自己多次，并且可以选择做一些额外的工作（所有这一切，除非你在基本情况下，在这种情况下完成的工作是不变的）。

在 Mergesort 中，f(n) = O(n) 因为合并两个已排序的子列表以生成包含所有子列表元素的单个排序列表所花费的时间与组合排序列表的大小成线性关系。

在Binary Search中，f(n) = O(1)因为每一步要做的只是比较目标值和待搜索子列表中间元素的值。

判断 f(n) 应该是什么的方法是进行所有递归调用，将任何参数的计算移到函数调用之外，然后用常量值替换递归函数调用.剩下的渐近与 f(n).

相同

Find the value of f(n) in the master theorem