这是我对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
然后我们将有如下计算步骤:
一。B:=B^2和E=10/2=5
2.P=P*(B^2)和E=5-1=4
三。b=b^4和e=4/2=2
三。b=b^8和e=1
四。P=P*B^10和E=0
把E增加到100然后我们将有:
B:=B^2和E=100/2=50
B:=B^4和E=25
P:=P*B^4和E=24
B:=B^8和E=12
B:=B^16和E=6
B:=B^32和E=3
P:=P*B^36和E=2
b:=b*b^32和e=1
B:=P*B^34和E=0
因此我们看到,将E的大小从10增加到100(10倍)并不会只增加5次迭代因此,复杂性被证明是O(log E)。

最佳答案

复杂性是O(logE)
注意,不可能一个接一个地有两个其他条件,所以在最坏的情况下,最多在两次迭代之后,e将减少一半,直到它变成0。
这意味着您最多需要2*log_2(E)迭代,这实际上是在O(logE)
注意,这不包括反复平方的算术运算,这可能会给方程增加另一个因子,因为当你完成时,b将在b中,这可能不是要计算的O((B^2)^logE) = O(B^(2logE)),这取决于O(1)的体系结构和实际大小。

关于algorithm - p = B ^ E的复杂度是多少?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/28925042/

10-11 23:12
查看更多