时间戳

首页 > 解决方案 > 递归除法函数的最坏情况时间复杂度？

c++ - 递归除法函数的最坏情况时间复杂度？

问题描述

给定这个算法：

void turtle_down(double val){
    if (val >= 1.0)
        turtle_down(val/2.0);
}

据我所知，T(n) = T(n/2) + O(1)。

O(1) 是基函数的最坏情况时间复杂度，即 val != 0.0（我说对了吗？）。然后递归调用给出了 T(n/2) 的时间复杂度，因为我们在递归调用之前除以 n。那正确吗？

但我不明白如何在这里做数学。我不知道我们将如何到达 O(log n)(base 2)。有人愿意解释或告诉我数学吗？

标签： c++timetime-complexitybig-o

解决方案

void turtle_down(double val){
    if (val != 0.0)
        turtle_down(val/2.0);
}

在上面的代码中，测试条件 if (val != 0.0)可能不会给你预期的结果。它会进入一个无限循环。考虑 val=32 的情况。可以看到，用 2 重复除法永远不会达到 0。

但是如果你用 say 替换测试条件，if (val >= 1)那么给定函数的递归关系将是 T(n) = T(n/2) + O(1)。

在这种情况下，时间复杂度为 T(n) = O(log n)。

要获得此结果，您可以使用主定理。

要理解给定的复杂性，请考虑 val = 32。您可以将 val 重复除以 2，共 5 次，直到它变为 1。注意 log 32 = 5。由此我们可以看到对该函数的调用次数为log n。

推荐阅读