algorithm - changetoBinary 算法的运行时间？

Question

我设计了一种算法，假设 n 是 2 的幂，将 10 的幂转换为二进制。我使用Gauss's Method来使用这个不错的方法的快速运行时间。为此，我将 n 除以 2 并将其发送到 Gauess 方法，如下所示:

changetoBinary(n)
if n=1
    return binary of 10 which is 1010

else

 return gauess(n/2,n/2)

很明显Guess方法会先分后胜再合。最后，我们将数字更改为二进制。现在我的问题是关于算法的运行时间:我的理解是，因为 Guess 运行时间是 Theta(n^log3(base2)) 我们可以说这个算法的运行时间也是一样的，因为大部分工作已经完成通过猜测。另一方面，当我试图找到递归关系时，我想出了 T(n/2)+O(n)，它是 Theta(n)，所以哪个是正确的？我在计算中遗漏了什么吗我会自相矛盾吗？

Answer 1

你的算法的递归关系不是T(n)=T(n/2)+n;

您算法的复杂度为 O(1)。所以你是对的，高斯函数的复杂性就是你的算法的复杂性。

如果您的算法是:change_to_binary(n){ change_to_binary(n/2);.....

那么 T(n)=T(n/2)本来是你的推荐。关系。