循環的時間複雜度

內循環執行時外循環執行n次？所以總的時間是n *。

我是否需要學習總結，如果是，那麼任何書都要參考？循環的時間複雜度

for(int i=1;i<=n;i++) 
    for(int j=1;j<=n;j+=i) 
    printf("*");

來源

2016-08-20 srbh

'printf（）'運行多少次，給定一個特定的值'n'？這是這對嵌套循環的時間複雜性。 –

@OllieJones所以你說的是一個給定的值k，時間複雜度是O（k）。讓我們說n = 5，內部循環執行5次i = 1，迭代i到2，內部循環執行3次，現在i = 3內循環執行2次，i = 4內循環執行2次。它因我而異。 – srbh

我認爲它會打印樓層（n/1）+樓層（n/2）+ ... +樓層（n/n）次。 – mm759

我相信那個時間的複雜性是O(n*log(n))。這是爲什麼：

讓我們選擇一些任意的自然數i，看看這個給定的i內循環需要多少步驟。對於這個我，你從j = 1到j < = n，並跳到我之間。所以基本上你正在做這個求和許多步驟：

summation = 1 + (1+i) + (1+2i) + ... (1+ki)

其中k是最大的整數，1 +き< = N。也就是說，k是步數，這就是我們想要解決的問題。那麼我們可以解決在平等導致k <= (n-1)/i因此k = ⌊(n-1)/i⌋。也就是說，k是(n-1)/i的floor函數/整數除法。由於我們正在處理時間複雜性，所以這個底線函數並不重要，所以我們將簡單地說出k = n/i。這是內循環對於給定的i所採取的步驟數。所以我們基本上需要將所有這些添加到i = 1到i < = n。

所以numsteps將是另外：

numsteps = n/1 + n/2 + n/3 + ... n/n 
     = n(1 + 1/2 + 1/3 + ... 1+n)

所以我們需要找到的1 + 1/2 +的總和...... 1/N來完成這一點。實際上這筆款項並沒有很好的關閉形式，但大約是ln(n)。你可以閱讀更多關於這個here。自integral from 1 to n of 1/x is ln(n)以來，您也可以猜測這個。再次，由於我們正在處理時間複雜性，我們可以用ln（n）來表示它的複雜性。因此我們有：

numsteps = n(ln(n))

所以時間複雜度是O(n*log(n))。

編輯：我的壞，我正在計算總和：P

來源

2016-08-20 12:45:41 gowrath

這個問題可以通過檢查來逼近：

n = 16 

i | j values   | # terms 
1 | 1, 2, ..., 16 | n 
2 | 1, 3, 5, ..., 16 | n/2 
.. | ..    | n/3 
16 | 16    | n/n

在上述表中，i是外環值，並且j values顯示內部循環的迭代。通過檢查，我們可以看到循環將採取n * (1 + 1/2 + 1/3 + ... + 1/n)步驟。這是一個有界的諧波系列。如this Math Stack Exchange article所示，上述表達式在n方面沒有關閉形式。但是，如this SO article所示，存在O(n*ln(n))的上限。

因此，您的兩個循環的運行時間爲O(n*ln(n))。

來源

2016-08-20 12:18:53

循環的時間複雜度

回答

相關問題