分析給定的程序

我給了一段代碼並告訴分析它。我感到很困惑。我需要計算foo運行多少次並使用它來確定n的函數。我知道foo運行了多少次，但我無法確定正確的功能。下面是代碼：分析給定的程序

j = 1; 
while(j <= n/2) 
{ 
    i = 1; 
    while(i <= j) 
    { 
     foo; 
     i++; 
    } 
    j++; 
}

我知道在哪裏的n一半被添加到運行模式foo運行。因此，例如，當n = 2，foo運行1時候，當n = 4，foo運行3時候，當n = 6，foo運行6倍，等等。事情是這樣的：

n = 2 runs -> j = 1 *   1 run 


n = 4 runs -> j = 1 * 
       j = 2 * *  3 runs 

n = 6 runs -> j = 1 * 
       j = 2 * * 
       j = 3 * * *  6 runs 

n = 8 runs -> j = 1 * 
       j = 2 * * 
       j = 3 * * * 
       j = 4 * * * * 10 runs

也許我只是在想這一點，但我一直盯着我的筆記本好幾個小時，試圖在遵循這種行爲的n方面提出一些功能。誰能幫忙？

編輯我還有一個問題。我怎麼知道這個函數是在Big-O還是Big-Theta？是否使用while循環代替for循環？

來源

2016-02-02 generic user007

重複http://stackoverflow.com/questions/35140945 –

「while循環而不是for循環」？我認爲你需要一個複雜性的入門書。複雜性僅取決於程序所執行的操作次數，而不取決於用於完成相同操作的實際迭代構造。意識到無論你使用for循環還是while循環，操作次數都是相同的。 – Aravind

我看到的一些例子使用'while'循環處理Big-O，因爲如果滿足某些條件它們可以儘早結束。例如，for（int i = 0; i <= n; i ++）'將運行n次，但while（i <= n &&！done）'可能不運行n次，因爲我們有條件'... &&！完成）'。由於它可能會提前結束，我們正在處理Big-O，因爲我們可以結束「小於或等於」「n」次。如果我們有一個循環會執行「n」次，那就意味着Big-Theta。這聽起來是對的嗎？ –

一旦我們認識到，大部分工作是由內而循環中完成，我們可以計算出運行時（對於一個給定的n）作爲次數內，而循環運行：

1+2+3+...n/2

這是由summation formula

= O（n ）。

來源

2016-02-02 02:32:04 Aravind

OP正在詢問_actual_運行次數，而不是大O命令。 –

這包括循環執行次數。這是第n/2個三角形數字。閉合形式（n/2）（（n/2）-1）/ 2，其是總和1 + 2 + 3 + ... + n/2。當然這是漸近二次的（由n^2支配）。如果我們在這裏是超技術的話，它實際上是：floor（n/2）（floor（n/2） - 1）/ 2，因爲整數除法的截斷。但通常考慮這些不重要的因素是不好的形式，因此大多數人會用O（n^2）來回答這個問題。 – ktbiz

j運行n/2次。對於每個這樣的迭代，運行i運行j次。對於每個這樣的迭代我，foo被調用。這樣的呼叫的數量是

∑ _{J =}^n/2個 [J] =（1 + N/2）π/ 4 = Θ（N ）。

這只是一個arithmetic series從1到n/2。

來源

2016-02-02 02:34:36

OP正在詢問_actual_運行次數，而不是大O次序。 –

謝謝，@DStanley - 我以某種方式懷疑最終目的不是增長的順序，而是更新了總和。 –

我得到'j'運行'n/2'次，對於每個這樣的迭代'i'運行'j'次。我對此感到困惑，我們得到了[[（1 + n/2）* n]/2'。我確實看到，因爲我們有另外一個'n'，所以Big-Theta命令的總數將是$ n^2 $。你怎麼知道給'1'加'n/2'，然後用'n'乘以'2'來除數？我正在抓幾個小時。 –

分析給定的程序

回答

相關問題