该算法的运行时复杂度？

Question

给定 a 和 b，我被要求以比 O(b) 更快的运行时间计算 a^b。我想到了：

if(b == 1) return a;
if(b % 2 == 0) 
    return findExp(a,b/2) * findExp(a,b/2);
else 
    return findExp(a,(b/2)+1) * findExp(a,b/2);

我的问题是，这个算法的运行时复杂度是对数时间还是多项式时间？

Answer 1

O(log(b))，所以是对数的。

Answer 2

你的算法是 O(b) 不是对数的。

在这部分代码 return findExp(a,b/2) * findExp(a,b/2); 中，您调用同一个函数，returns 两次调用相同的值。基本上，您正在为第二次通话花费多余的时间。

在数学上，如果根据您的算法 T(b) 表示 a^b 所需的时间，则它是 T(b) = T(b/2) + T(b/2)，其中每个术语对应于每个调用。 T(b) = 2.T(b/2)。解决这个递归，你会得到T(b)的顺序是b.

要使其成为对数，只需将值存储在变量中以防止冗余调用。

编辑后的代码：

if(b == 1) return a;
if(b % 2 == 0) 
    int x = findExp(a,b/2);
    return x*x;
else 
    int x = findExp(a,b/2);
    return a*x*x;

现在 T(b) = T(b/2) 因为你只调用 findExp(a,b/2) 一次（在 if 部分或 else 部分）。

这给你O(log(b))算法

如果你想测试它，运行你的代码和我提到的一些大 b 的代码，假设 b = 1000000000 并对比所用的时间。

Runtime complexity of this algorithm?