如何确定此算法的时间复杂度？

以下函数计算a^b。假设我们已经有一个包含所有需要的素数的prime_list，并且从小到大排序。代码是用python编写的。如何确定此算法的时间复杂度？

def power(a,b): 
    if b == 0: 
     return 1 

    prime_range = int(sqrt(b)) + 1 
    for prime in prime_list: 
     if prime > prime_range: 
      break 
     if b % prime == 0: 
      return power(power(a, prime), b/prime) 

    return a * power(a, b-1)

如何确定其时间复杂度？ p.s.代码并不完美，但您可以看到这个想法正在使用素数来减少算术运算的次数。我仍在寻找一个理想的实现，所以请帮助，如果你拿出一些东西。谢谢！

来源

2015-08-08 YZhQ

你在用什么语言？您可以以编程方式测量运行时间。 –

即使您的语言的sqrt（）也是基于实现的。除非您提供所需的详细信息，否则无法找到此功能的整体复杂性。 –

你真的想测量时间复杂度吗？反对“如何确定时间复杂性”或“如何测量运行时间”？ – Stef

最糟糕的情况，当循环是exausted。但在这种情况下，b在下一次递归调用中被除以2。

在最坏的情况下，我们通过因子2在约SQRT devide B（b）在每个步骤，直至b将手伸1.
因此，如果我们设定方程

操作

F（1）= 1和f（n）的= F（N/2）+ SQRT（N）

我们得到using woflram alpha

F（N）=（1个+ SQRT（2））（SQRT（2）SQRT（N）-1）
那就是
O（sqrt（b））

来源

2015-08-08 13:41:04

如果你想要递归的实际证明（没有wolfram alpha），你只需要'sqrt（n）+ sqrt（n/2）+ sqrt（n/4）+ sqrt（n /（2^log2因为'2^log2（n）= 1'），这就是'sqrt（n）* sum（（1/sqrt（2））^ I）'，其中'I = 1..log2 （n）'，使用几何系列总和的公式，得到所需的答案;） – Holt

如果'b'是素数，则不会被2除。 –

@Juan Lopes如果b是素数，则在sqrt（b）操作之后，第一个循环会被检验（有条件检查素数

如何确定此算法的时间复杂度？

回答

相关问题