這個算法的時間複雜度是多少？

public static void Comp(int n) 
{ 
    int count=0; 
    for(int i=0;i<n;i++) 
    { 
     for(int j=0;j<n;j++) 
     { 
      for(int k=1;k<n;k*=2) 
      { 
       count++; 
      } 
     } 
    } 
    System.out.println(count); 
}

有誰知道時間複雜度是多少？這個算法的時間複雜度是多少？

，什麼是好大哦（）

請ü可以解釋這樣對我，一步一步？

來源

2015-04-07 AM3

你的猜測是什麼。 –

我認爲這是N^2 * logN。 –

誰給你這個問題幾乎可以肯定是尋找答案n^2 log(n)，以供其他解釋的原因。

但是這個問題沒有任何意義。如果n > 2^30,k會溢出，使內循環無限。

即使我們把這個問題作爲完整的理論，並承擔n，k和count不是Java int S，但是一些理論整數類型，答案n^2 log n假定操作++和*=有恆定的時間複雜度，無論需要多少比特來表示整數。這個假設並不真正有效。

編輯

有人向我指出在下面的意見的基礎上，這樣的硬件工程，它是合理地假設++，*=2和<都有固定的時間複雜度，不管需要多少位。這會使我的答案的第三段無效，但請不要對我的答案進行投票 - 現在我無法刪除它已被接受！

來源

2015-04-07 16:52:07

這通常是假設，這是不正確的。乘以2只是硬件中的移位操作，'++'只是一個計數器，它是一個恆定的時鐘週期。請查閱http://teahlab.com/，尤其是櫃檯文章/電路。所以這個問題不像你想象的那樣理論化。在硬件中，假設是正確的。 –

接受此作爲答案顯示OP是如何迷路和困惑。這個問題並不像這個人所假設的那樣理論化，他只是提到其他答案是正確的。那麼這是正確的答案？有點想法，朋友。有點思考。 –

@KonsolLabapen對於移位操作（即乘以2），並行訪問移位寄存器是否工作？ http://teahlab.com/4-Bit_Parallel_Access_Shift_Register/我去了網站搜索單詞「shift」，這就是出現了。 –

時間複雜度爲O(n^2 log n)。爲什麼？每個for-loop是n的函數。你必須爲每個for循環乘以n;除了增長爲log n的內部循環。爲什麼？對於每次迭代，k乘以2.考慮合併排序或二叉搜索樹。

細節

對於前兩個循環：1求和從0到n，其爲n + 1等的第一兩個環得到(n+1)*(n+1)= n^2+2n+1= O(n^2)

用於第k循環中，我們的K成長爲1,2,4,8,16,32，......以至於2^k = n。以雙方的日誌和你得到k=log n

再次，不清楚？

enter image description here

所以，如果我們設置m=0，並a=2然後我們得到-2^n/-1爲什麼是= 2？因爲這是系列產量爲2,4,8,16的一個值，... 2^k

來源

2015-04-07 16:19:19

不正確，最內層for循環需要log（n），從而使最終產品O（n^2 log（n）） – Lalaland

他可能希望能夠給出的最緊密的界限，而這不是。 –

@Lalaland這沒什麼不正確的，它並不嚴密。 –

理論上這是O(n^2 * log(n))。

每兩個外循環是O(n)，而內層是O(log(n))，因爲nlog base 2是的，你必須通過2分n得到1次數。

而且這是一個嚴格的約束，即代碼也Θ(n^2 * log(n))

來源

2015-04-07 16:23:45 pkacprzak

這個算法的時間複雜度是多少？

回答

相關問題