ALGO(A,s,d)
m=d-s+1
if m>=2 then
q=⌊m/2⌋
return 2ALGO(A, s, s+q-1) + 3ALGO(A, s+q, d);
else
return 1
endif
我有这段代码，我必须找到 函数中的递归关系n。问题指出该算法最初用 调用ALGO(A, 1, n)。A 是一个大小为 的数组n，s并且d是整数，q是 的 floor 函数m/2。
我想到的解决方案是：
T(n) = 1 if n<2
T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + theta(1) if n>=2.
我的理由是if s=1，在第一个递归调用中，我有d=n，所以，对于第二个调用，所以，因为在 if 中我计算了哪些成本。我不知道我想出的解决方案是否正确m=n，也不知道如何解决它。对于解决方案，我不知道我是否可以说。q=⌊n/2⌋s=1d=⌊n/2⌋m=⌊n/2⌋s=s+q=1+⌊n/2⌋ d=nm=⌈n/2⌉T(⌊n/2⌋) + T(⌈n/2⌉) + theta(1)q1T(⌊n/2⌋) + T(⌈n/2⌉) = T(n)
您给出的递归关系是正确的，尽管基本情况也应该有 θ(1)：𝑇(1) 的值不是返回值 (1)，而是返回它所需的工作（时间复杂度），即 θ(1)：
𝑇（1）= θ（1）
𝑇（𝑛）= 𝑇（⌊𝑛/2⌋）+ 𝑇（⌈𝑛/2⌉）+ θ（1）
您不能跳转到恒等式 𝑇(⌊𝑛/2⌋) + 𝑇(⌈𝑛/2⌉) = 𝑇(𝑛)，因为这只是没有 θ(1) 项的递归情况的镜像符号，但在删除该 θ(1) 项之前，您应该说明为什么可以这样做。
解决此问题的方法之一是观察递归树是一棵完整的二叉树。例如，对于 𝑛=11，我们可以按如下方式描述该二叉树，仅显示 𝑠 和 𝑑 参数的值：
该树的叶子表示
return 1执行的基本情况，而内部节点表示执行两个递归调用的情况。每条边代表一次递归调用。
显然，当 𝑠 等于 𝑑 时以及 𝑠 在 1 和 𝑛 之间的每个可能值时，都会执行基本情况。因此有 𝑛 个叶子。在任何满二叉树中，内部节点的数量都比叶子的数量少一个，这意味着树有 2𝑛-1 个节点和 2𝑛-2 条边。每个节点和每条边代表 θ(1) 复杂度，因此总的来说，该算法的时间复杂度为 θ(𝑛)。
换句话说：因为内部节点的数量与叶子的数量是同一个量级，所以你可以从递归情况中省略 θ (1) 项。