時間複雜度

可有人請向我解釋如何計算下列遞歸代碼的複雜性：時間複雜度

long bigmod(long b, long p, long m) { 
    if (p == 0) 
     return 1; 
    else 
    if (p % 2 == 0) 
     return square(bigmod(b, p/2, m)) % m; 
    else  
     return ((b % m) * bigmod(b, p - 1, m)) % m; 
}

來源

2011-04-19 station

這O（日誌（P）），因爲你是除以2每次或減去一個然後除以二，所以最壞的情況下會真的取O（2 * log（p）） - 一個用於除法，一個用於減法。

請注意，在這個例子中，最壞情況和平均情況應該是相同的複雜度。

來源

2011-04-19 04:45:31

它運行在O(log n)

沒有昂貴的操作（通過我的價格比平方或改裝，無循環等）的功能裏面，所以我們可以非常簡單，只是算函數調用。

最好的情況是兩個冪，我們將需要完全的log（n）調用。

最糟糕的情況是，我們每隔一個電話會收到一個奇數。這隻能做我們的呼叫的兩倍。乘以一個常數因子，不會漸近地變壞。 2*f(x) is still O(f(x))

O(logn)

來源

2011-04-19 04:45:58

分割如果數字爲負你從中減去1，它變得比除以2正，所以它不能被登錄（ n）甚至在更糟糕的情況下。 – 2011-04-19 04:48:03

我沒有遵循，你可以再試一次嗎？如果哪個數字是負數？我認爲我們的答案几乎是一樣的東西，我沒有看到差異 – 2011-04-19 04:52:43

因此，p是正數比我們除以2，或負數比我們減去一個，並且必須在之後除以兩。 – 2011-04-19 04:55:11

如果你想更正式的關於它，那麼你可以寫一個遞推關係，並使用主定理來解決它。 http://en.wikipedia.org/wiki/Master_theorem

來源

2011-04-19 04:51:12 Adam

它是爲O（log（N））基體2，因爲通過2

來源

2013-03-12 19:45:38

我認爲你應該添加一個解釋爲什麼這樣。 – 2013-03-12 20:05:15

你能展示你是如何提出答案的？ – 2013-03-12 20:05:27

回答

相關問題