分析程序

Question

我想知道如果任何人都可以向我解釋分析程序的語義。我知道如何做簡單的，但是有一些更復雜的我不知道該怎麼做。例如，這是我書中的一個問題。我們給出6個小片段，並告訴他們分析：

(1). sum = 0; 
     for(i = 0; i < n; ++i) 
      ++sum; 

(2). sum = 0; 
     for(i = 0; i < n; ++i) 
      for(j = 0; j < n; ++j) 
       ++sum; 

(3). sum = 0; 
     for(i = 0; i < n; ++i) 
      for(j = 0; j < n * n; ++j) 
       ++sum; 

(4). sum = 0; 
     for(i = 0; i < n; ++i) 
      for(j = 0; j < i; ++j) 
       ++sum; 

(5). sum = 0; 
     for(i = 0; i < n; ++i) 
      for(j = 0; j < i * i; ++j) 
       for(k = 0; k < j; ++k) 
        ++sum; 

(6). sum = 0; 
     for(i = 1; i < n; ++i) 
      for(j = 1; j < i * i; ++j) 
       if(j % i == 0) 
        for(k = 0; k < j; ++k) 
         ++sum; 

我明白了1，2，和4那些部分是容易的。我沒有得到的是3,5和6.

1運行n次，所以一個在Big-Oh(n)。 2有兩個for環路，每個環路運行n次，因此這一個是Big-Oh(n^2)。 4是我以前見過的東西。內循環的運行次數與i的值相同。所以，如果i = 1然後循環運行一次，如果i = 2的環路的1 + 2 + 3 + ... + n一個patters這意味着這整個這是Big-Oh(n^2)模式運行兩次。我不確定如何在條件中使用n * n約3。這也是我不確定如何在那裏也會用i * i去約5的原因。至於6，我們不僅有i * i，但也有一個if聲明，可能會或可能不會運行。我該怎麼做？任何人都可以幫助解釋如何做那些？謝謝。

UPDATE我靈機一動約3.在一個環路外運行n倍，內部的循環運行n^2倍。那麼對於那個，我們會有n * n^2這是n^3？那麼那個會在Big-Oh(n^3)？

Answer 1

你想通第三個了。同樣的推理適用於所有人。其實你的目標是根據n找到sum的最終值。

對於第五之一，即是要找到的總和：Σ _{I = 0}^Ñ（Σ _{J = 0}^{N^2}（J））

內求和只是（ⅰ *（ⅰ + 1））/ 2，這是從the simple summation formula如下。

然後，你必須Σ _{I = 0}^Ñ（ⅰ *（ⅰ + 1））/ 2，它等於[Σ _{I = 0}^Ñ（ⅰ）+Σ _{I = 0}^ñ（ⅰ）]/2。

這是O（N ）升ooking在主導項Σ _{I = 0}^ñ（我），你可以認爲作爲一個整體，所以你只是增加了指數，你得到N個。第六個是作爲一個練習，想象一下sum到底會是什麼。