algorithm - p = B^E 的复杂度是多少？

Question

这是我对 p = B^E 的解决方案

p,b,e:= 1,B,E
  WHILE e!=0 DO
  IF e is EVEN THEN
    b:= b^2
    e:= e/2
  ELSE
    p:= p*b
    e:= e-1
  FI
 OD.

现在，在我看来，循环运行了 E 次，复杂度为 log n。我说得对吗？

下面是我将如何解释复杂性:

解释:在最坏的情况下，循环将运行 E 次，但对于每个遇到的偶数，e 减半 2，从计算中消除一个元素因子，因此当输入时，计算的大小不会呈指数增长尺寸变大。因此，该算法的复杂度为O(log(E))。

例子:让我们设置 E = 10然后我们将有如下计算步骤:1. b := b^2 和 e = 10/2 = 52. p = p*(b^2) 和 e = 5-1 = 43. b = b^4 和 e = 4/2 = 23. b = b^8 和 e = 14. p = p*b^10 和 e = 0

让我们将 E 增加到 100。然后我们将有:

1. b := b^2 和 e = 100/2 = 50
2. b := b^4 和 e = 25
3. p := p*b^4 和 e = 24
4. b := b^8 和 e = 12
5. b := b^16 和 e = 6
6. b := b^32 和 e = 3
7. p := p * b^36 和 e = 2
8. b := b * b^32 和 e = 1
9. b := p * b^34 和 e = 0因此我们看到，将 E 的大小从 10 增加到 100，即 10 倍不会将迭代次数仅增加 5。因此，复杂性被证明为 O(log E)

Answer 1

复杂度为 O(logE)。

注意不能有两个ELSE条件依次出现，所以在最坏的情况下，最多迭代两次后，e会减半，直到变成0。

这意味着您最多需要 2*log_2(E) 次迭代，这确实在 O(logE)

中

---

请注意，这不包括反复对 b 求平方的运算，这可能会在等式中添加另一个因素，因为完成后，b 将是在 O((B^2)^logE) = O(B^(2logE)) 中，这可能不是要计算的 O(1)，具体取决于架构和 B,E 的实际大小。