algorithm - 以下函数作为递推关系过程的复杂性是多少？你能解释一下步骤吗？

Question

以下函数作为递推关系过程的复杂性是多少？你能解释一下步骤吗？

void test(int x){

    if(x <=0) return;
    System.out.println(x);
    test(x/2) + test(x/3);

}

标签： algorithmtime-complexityrecurrence

Answer 1

在函数内部，您有一个基本情况 (x<=0)，然后您有一个 O(1) 操作（打印），然后您递归调用该函数。

您将获得以下功能：

T(n) = T(n/2) + T(n/3) + O(1)

您现在如何从这里导出 O 符号？

考虑下图：

这是公式的递归树。

左侧每次除以 2，即高度，即最左侧路径中的度数为 log_2(n)。这也是三者中最长的路径，因为它是“最慢的”。总是只除以 2（而不是 3），稍后会得到最好的情况。

最右边的路径是 log_3(n)。这也是三者中最短的路径，因为它是“最快的”。总是只除以 3（而不是 2），将更快地得到最好的情况。

现在，让我们计算每个度数的值的总和。第一度显然是 1。第二度小于 1。很明显，对于每个度，值的总和 <=1。

解决方案将是所有树的所有值的总和。我们如何获得它？我们可以将度数乘以每个度数的值之和。

我们知道最坏的情况是O(log_2(n)*1) = O(log_2(n))，最好的情况是Ω(log_3(n) 1) = Ω(log_3(n))。这就是答案。