爲什麼這個循環需要O（2^n）時間複雜度？

有一個循環執行蠻力算法來計算5 * 3而不使用算術運算符。爲什麼這個循環需要O（2^n）時間複雜度？

我只需要添加五次3次，這樣就需要O（3），如果輸入是x * y，那麼就是O（y）。但是，在一本書中，它表示需要O（2^n），其中n是輸入中的位數。我不明白爲什麼使用O（2^n）來表示它O（y）。它是更好的方式來顯示時間複雜性？你能解釋我嗎？

我不要求其他算法來計算這個。

int result = 0 
for(int i=0; i<3; i++){ 
    result += 5 
}

來源

2017-08-06 devDNA

運行時是一個常量（O（1）），因爲此循環的運行時不依賴於任何外部參數。這真的是這本書所說的嗎？你能否引用特定的措詞以及它所指的是什麼？ – templatetypedef

你在談論「輸入中的位數」我高度懷疑你正在捨棄一些關於本書所說的相關信息。 – bolov

在一本書中，它表示「要形成5x3，我們將從0開始並重復添加5.時間複雜度非常高，與O（2^n）一樣多，其中n是輸入中的位數」。但是3是0011，這是什麼意思n是位數？爲了表示3，它只需要2位。 O（2^2）= O（4）。爲什麼作者使用O（2^n），其中n是輸入中的位數，而不是O（n）？ – devDNA

我認爲你誤讀了本書的內容。

當本書談論計算兩個數的乘積的算法時，它使用乘以3 × 5的示例作爲通過添加y + y +來計算x × y的更一般概念的具體實例。 .. + y，x總次數。它並沒有聲稱具體的算法「add 5 + 5 + 5」在時間O上運行（2 ⁿ）。相反，想想這個算法：

int total = 0; 
for (int i = 0; i < x; i++) { 
    total += y; 
}

該算法的運行時間是O（x）。如果按照本書的建議測量運行時間作爲數字x中的位數n的函數 - 那麼運行時間爲O（2 ⁿ），因爲要表示您需要的數字x（log n ）位。這是polynomial time and pseudopolynomial time之間的區別，並且該書隨後描述用於解決該問題的更好算法的原因在於，運行時最終成爲用於表示輸入而不是的位數的多項式數字的數字值爲。關於小學數學乘法和加法的論述可以幫助你更好地理解這兩個量之間的差異。

來源

2017-08-06 22:22:26 templatetypedef

謝謝你的回答。與本書不同，我使用數值來表示時間複雜度。嗡嗡聲..我是否必須使用用於表示時間複雜度的數字位數？ – devDNA

這取決於上下文。把頭腦區分開來是一個不錯的主意，特別是如果你正在處理可以任意大的輸入。 – templatetypedef

啊。好的。感謝您的時間和幫助。 – devDNA

不要以爲用3和5想想如何計算2十億×2十億（大約2^31乘以2^31）

你輸入的31位各（N）和您循環將執行20億次，即2^N。

所以書是正確的。對於5x3的情況，3是2位。所以它的複雜性是O（2^2）。再次糾正。

來源

2017-08-06 22:14:55 xycf7

雅。我知道給定的運行時也是正確的，但我只是想知道爲什麼它使用O（2^n）來表示它O（y）。這是更好的方式來顯示時間複雜性嗎？ – devDNA

基本上是。這是展示覆雜性的更好方法。讓我詳細說明一下：初始複雜性分析始於圖靈機（使用磁帶輸入），由於狀態不變，複雜性主要取決於輸入的長度。和輸入可以在任何鹼基（基體2，基體10，基體36等），但分析在基座完成2所表示的輸入端，因此複雜的數字不同的機器之間/算法可以是相當的。現代計算機也建立在二進制系統之上，幾乎在任何地方使用二進制都更有意義。 – xycf7

您聲稱輸入的時間複雜度爲O（y），並且該書聲稱輸入中的位數的時間複雜度爲O（2 ⁿ）。好消息：你們都是對的！如果數字y可以用n位表示，y至多爲2 ⁿ - 1

來源

2017-08-06 22:16:17 Ryan

爲什麼這個循環需要O（2^n）時間複雜度？

回答

相關問題