以下代碼的複雜程度如何？

根據此代碼：以下代碼的複雜程度如何？

for (int i=1; i<=N; i*=2) 
{ 
    for (int j=1;j<=i;j++) 
    { 
    System.out.println("The value for i is "+i+" and the value for j is "+j); 
    } 
}

第一for-loop將首先運行log(n)倍，我想到2n-1第二for-loop，但它並不適用於奇數工作。

任何想法？ :)

來源

2014-11-17 user3813409

這是第一個循環執行的次數（'log（n）'）乘以第二個循環執行的次數（'i'）。 – Charlie

你想要漸近複雜性還是迭代次數？漸近線是n * log（n） –

我需要考慮任何一行的迭代次數，而不是找到O符號。 – user3813409

你的第一個for循環得到了i作爲一個系列：

enter image description here

x看臺：當這個系列的最後一個元素是比格爾或等於n，

enter image description here

第一循環停止第一個循環執行多少次。現在，我們正在努力尋找x：

enter image description here

其中

enter image description here

是的，它是如你所說：

第一個for循環運行的log（n ）次

第二個for循環體運行的總和：

enter image description here

這證明你的算法有O（n）的複雜性

您的打印發生2N-1時候，如果N是1： 1, 2, 4, 8, ... , 2^n

這是表面分析，但它做的工作。

來源

2014-11-20 11:31:09 Everettss

當i = 1，內環將運行1次
當i = 2，內環將運行2次
當i = 4，內環將運行4次
...
當i = N，內環將運行N次

打印語句執行1 + ... + N/4 + N/2 + N次，這是O（n）。

來源

2014-11-17 15:07:24 Maroun

'O（n）'是正確的，但是這個證明（這種證明形式）只適用於'2^n-1' –

@DmitryGinzburg從上面和下面通過下一個2的冪來界定。 –

@ G.Bach值得一提的答案 –

以下代碼的複雜程度如何？

回答

相關問題