递归算法的时间复杂度
有人可以向我解释一下如何计算以下递归代码的复杂度：
long bigmod(long b, long p, long m) {
if (p == 0)
return 1;
else
if (p % 2 == 0)
return square(bigmod(b, p / 2, m)) % m;
else
return ((b % m) * bigmod(b, p - 1, m)) % m;
}
Can someone please explain to me how to calculate the complexity of the following recursive code:
long bigmod(long b, long p, long m) {
if (p == 0)
return 1;
else
if (p % 2 == 0)
return square(bigmod(b, p / 2, m)) % m;
else
return ((b % m) * bigmod(b, p - 1, m)) % m;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这是 O(log(p)) 因为你每次都除以 2 或减一然后除以二，所以最坏的情况实际上需要 O(2 * log(p)) - 1为除法，一为减一。
请注意，在此示例中，最坏情况和平均情况应该具有相同的复杂度。
This is O(log(p)) because you are dividing by 2 every time or subtracting one then dividing by two, so the worst case would really take O(2 * log(p)) - one for the division and one for the subtraction of one.
Note that in this example the worst case and average case should be the same complexity.
如果你想更正式地解决这个问题，那么你可以编写一个递推关系并使用 Master 定理来解决它。 http://en.wikipedia.org/wiki/Master_theorem
If you want to be more formal about it then you can write a recurrence relation and use the Master theorem to solve it. http://en.wikipedia.org/wiki/Master_theorem
它的运行时间为 O(log n)
函数内部没有昂贵的操作（因此我比平方或取模更昂贵。没有循环等），所以我们几乎可以只计算函数调用。
最好的情况是 2 的幂，我们将需要恰好 log(n) 次调用。
最坏的情况是，我们每次拨打电话时都会收到奇数号码。这最多只能使我们的调用增加一倍。乘以一个常数因子，渐近不会更糟。
2*f(x) 仍然是 O(f(x))O(logn)It runs in
O(log n)There are no expensive operations (by that i more expensive than squaring or modding. no looping, etc) inside the function, so we can pretty much just count the function calls.
Best case is a power of two, we will need exactly log(n) calls.
Worst case we get an odd number on every other call. This can do no more than double our calls. Multiplication by a constant factor, no worse asymptotically.
2*f(x) is still O(f(x))O(logn)它是以 2 为底的 o(log(N))，因为除以 2
It is o(log(N)) base 2, because the division by 2