RunTime我的電源方法的複雜性

如果電源是偶數，我方形基部，和劃分功率除以2
如果電源是奇數，我遞歸運行的方法，用功率減小減1，以得到偶數，然後乘以基數得到的結果，以計算減1的功率。
基本情況達到時，功率爲1，結果爲0。

我的問題是，什麼是這種方法的時間複雜度？因爲，我們在每次迭代中將權力除以2，是否記錄到基數2？

 double myPow(double base, int pow) { 
     if(pow == 0) 
      return 1; 

     if(pow < 0) 
      return 1/base * 1/myPow(base, (pow*-1)-1); 

     if(pow %2 == 1) 
      return base * myPow(base, pow-1); 
     else 
      return myPow(base*base, pow/2); 
    }

來源

2017-07-27 PepperBoy

是的，你是對的 – sunkuet02

是的，複雜性是對數的。你的方法本質上是exponentiation by squaring

平方的數量等於pow的二進制展開中的零的數量，並且乘法的數量等於pow的二進制展開中的個數，所以總的操作數量大約是冪的有效位數log2(pow)

來源

2017-07-27 05:31:12 MBo

你的想法是正確的，這個冪方法是O（log n）。請注意，我沒有包含此日誌的基礎（在本例中爲基數2），這是因爲all logs differ by a constant。

MBo給出了上面的簡要說明，爲什麼會出現這種情況，但我想進一步詳細瞭解爲什麼會出現這種情況。

首先，我們需要確定此方法的運行時間依賴於什麼。注意，無論基礎是什麼，如果功率相同，運行時間將是相同的（給予或者採取無關緊要的隨機性）。但是，當功率改變時，運行時間將根據MBo所述改變有效位的數量。

但這是什麼意思？那麼，考慮這兩種情況下（讀二進制這些任務，我使用僞代碼這裏）：

case 1: 
pow = 1000 

case 2: 
pow = 1111

你會發現，這兩種情況對於給定比特數的最好和最壞的情況。第一個允許我們整齊地除以2，直到我們碰到基本情況，另一個讓我們在除以2之前減1，導致第一次的操作次數的兩倍。由於大O是關於最壞情況的時間複雜度，讓我們更深入地研究最壞的情況（考慮到第一個整齊地導致我們記錄n次）。我們必須執行與最佳情況相同數量的劃分，但是每個劃分都需要減法。這意味着我們以2 * log n結束。然而，正如我上面所說的，大O不關心常量，所以我們漸漸地以O（log n）時間結束。這意味着有效位數（或數字位數）限制了需要執行的操作數（位< = ops < = 2 *位）。

我希望這能讓你對問題有更多的瞭解。如果你沒有得到任何其他的東西，請記住，大O不關心常量，無論它們在哪裏。

來源

2017-07-27 16:43:12 UnknowableIneffable

RunTime我的電源方法的複雜性

回答

相關問題