1

我设计了一个算法来将 10 的幂转换为二进制,假设 n 是 2 的幂。我使用高斯方法来使用这种好方法的快速运行时间。为此,我将 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) 那么哪个是正确的?我在计算中是否遗漏了某事我会矛盾吗?

4

1 回答 1

1

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

你的算法的复杂度是 O(1)。所以你是对的,高斯函数的复杂性将是你算法的复杂性。

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

那么 T(n)=T(n/2) 将是您的推荐。关系。

于 2014-02-21T07:44:02.437 回答