我设计了一个算法来将 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) 那么哪个是正确的?我在计算中是否遗漏了某事我会矛盾吗?