如何確定此算法的時間複雜度？

以下函數計算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）操作之後，第一個循環會被檢驗（有條件檢查素數

如何確定此算法的時間複雜度？

回答

相關問題