以下嵌套循環依賴關係的時間複雜度是多少？

count=0; 
for(i=1;i<=n;i*=5) 
    for(j=1;j<=i;j++) 
     count++;

根據我目前所瞭解的內容，內環將增加5的冪數，就像我在下面的表格中所描述的那樣，即當i = 1，j = 1時，當i = 5，j = 5和等等。以下嵌套循環依賴關係的時間複雜度是多少？

i | 1 | 5 | 25 | 125 |

j | 1 | 5 | 25 | 125 |

這使j增加，如在5^0,5^1,5^2,5^3等等。使用高斯特技，1 + 2 + 3 + 4 ... + n =（n 2 + n）/ 2 = n 2/2 + n/2，這給出了5 ^（（n 2 + n）/2）。

這是否使總運行時間O（log base（5）n）？

來源

2017-04-09 Tia

我們會考慮循環，其中內循環的迭代次數是獨立於外環的指數值

然後我們會盡量的n不同的情況，以找出正確的模式：

n = 5

外：1 5

內：

i = 1：1次

i = 5：5次

1 + 5 = 6次，k = 2

n = 25

外：1 5 25

內：

i = 1：1次

i = 5：5次

i = 25：25倍

1 + 5 + 25 = 31次，k = 3

n = 125

外：1 5 25 125

內：

1 + 5 + 25 + 125 = 156次，k = 4

inn ER：

(1 + ... + n/5^2 + n/5^1 + n/5^0) 

n(1/n + ... + 1/5^2 + 1/5^1 + 1/5^0) 

n(1/5^k-1 + ... + 1/5^2 + 1/5^1 + 1/5^0) 

O(n(1/5^k-1 + ... + 1/5^2 + 1/5^1 + 1/5^0))

= O（n）的

最後你可以從我們計算時間複雜度爲爲O（n）格局看。

鏈接，時間複雜度解決方案的論證與等比數列： https://justpaste.it/15fhs

來源

2017-04-10 01:18:14 Oghli

處測試n的不同情況時，我得到的模式完全相同，這很好看，括號中的因子是一個常數 – gartenkralle

你可以請我解釋一下，它是如何變成O（n）使用幾何級數的公式？ – Tia

是的，你可以從幾何級數推斷時間複雜度看到更新的答案鏈接。 – Oghli

這裏不能直接應用公式1 + 2 + … + n = n(n+1)/2。 5^0 + 5^1 + … + 5^m和5^(0 + 1 + … + m)是兩個完全不同的東西。

該系列5^0 + 5^1 + … + 5^m是geometric series。使用式應該是

這意味着5^0 + 5^1 + … 5^m = O(5^m)。還請注意5 ^m = n。

來源

2017-04-09 21:06:54 kennytm

這是錯誤的。你忽略了對數行爲。 – gartenkralle

@gartenkralle你的意思是什麼？ – kennytm

總和不應該運行到（n-1）。它應該運行到log（n）。由於那個結果是不同的。 – gartenkralle

您必須從m = 0到小於2n的log5（n）之和5^m。所以運行時間在O（n）。

例如，如果n = 125，則總和爲156（< 2n）。

對於任何n，總和小於2n。

來源

2017-04-09 21:56:47 gartenkralle

你是對的，當我在你的最後一行代碼行的內循環 – Oghli

以下嵌套循環依賴關係的時間複雜度是多少？

回答

相關問題