漸近最差情況下的運行時間。需要一些說明

對於下面mystery(n)函數的僞代碼，請在其漸近最差情況下的運行時間f(n)中找到緊密的上限和下限。也就是說，找到g(n)這樣f(n) ∈ Θ (g(n))。（假設n爲正整數）漸近最差情況下的運行時間。需要一些說明

Mystery (n){     
c ←1       | (constant) 
for i ←1 to n     | n 
    do for j ←i to n   | j 
    do for k ← n down to n/2 | n/2 
     do c ← c + 1   | (constant) 
print c      | (constant) 
}

總時間：（N/2），新澤西州（在此不知道）

就在身邊的時間標記是什麼，我想通了迄今。對於這個問題，最佳和最差情況下的運行時間沒有區別？另外，我怎樣才能找到這種方法的上限和下限？任何建議都會很棒。或者我可以做一些閱讀的資源，因爲我的教科書在這個主題上非常模糊。

來源

2014-09-29 Mike Meding

試着把它寫成外層循環'（n^2/2 +（n-1）* n/2 + ...）的操作總和' – RishiG 2014-09-29 16:05:57

j不應該在您的公式中，因爲j也是n的函數。

每當你有一個依賴外循環變量的循環時，我覺得最容易看看求和公式來找到複雜性。

所以外層循環肯定運行n次，而最內層循環肯定運行n/2次，但一般來說n/2 ∈ O(n)。

讓我們來看看中間循環。

中間循環在第一次迭代中運行(n-1)次，然後在第二次迭代中運行(n-2)次，一直到(n-n)，這等於0次。您可以將這些術語重新排列爲0到n之和。我們知道這個總和等於n(n+1)/2。

由於該公式表示外層和中層循環的組合，因此您可以簡單地乘以最內層循環以獲得最終公式n(n+1)n/(2*2) == n^2(n+1)/4。

你應該認識到的一個概念上的事情是，因爲c只是一個計數器，並且在每次迭代時遞增，所以可以認爲c是該算法的運行時複雜度的直接表示。

您可以通過計算c來驗證此結果。下面是C語言編寫的證明這種算法的示例程序：

#include <stdio.h> 
#include <stdlib.h> 

int main(int argc, char *argv[]) { 
    int c = 0; 
    int n = 10; 
    if (argc > 1) { 
    n = atoi(argv[1]); 
    } 
    for (int i = 1; i <= n; ++i) { 
    for (int j = i; j <= n; ++j) { 
     /* Note that I've changed k to run from 0 to n/2 instead of n 
     down to n/2, but this doesn't change the result. */ 
     for (int k = 0; k < n/2; ++k) { 
     ++c; 
     } 
    } 
    } 
    printf("c == %d; n^2(n+1)/4 == %d\n", c, n*n*(n+1)/4); 
}

這裏的從上述程序的輸出爲輸入2，4，8，32和64：

c == 3; n^2(n+1)/4 == 3 
c == 20; n^2(n+1)/4 == 20 
c == 144; n^2(n+1)/4 == 144 
c == 8448; n^2(n+1)/4 == 8448 
c == 66560; n^2(n+1)/4 == 66560

來源

2014-09-29 15:54:37 b4hand

這非常有幫助！謝謝！雖然我的確有一個問題與你的答案有關。把這個用大寫字母表示法來表示，我會簡單地使用結果公式中最重要的術語是正確的？這樣n^3 * n^2將是n^3，因爲它對於足夠大的數據集是最重要的。 – 2014-09-29 20:09:18

是的，只要你的意思是（n^3 + n^2）而不是（n^3 * n^2）就是這樣。我會認爲這是一個錯字，但以防萬一（n^3 * n^2）將是n^5。 – b4hand 2014-09-29 20:27:11

是的，我寫錯了。在簡化結果公式之後，您將以n^3作爲最重要的術語。 – 2014-09-29 21:54:30

Mystery (n){     
c ←1       | (constant) 
for i ←1 to n     | n 
    do for j ←i to n   | j 
    do for k ← n down to n/2 | n/2 
     do c ← c + 1   | (constant) 
print c      | (constant) 
}

你對正在運行n次的外循環是正確的。然而，下一個循環將對i = 1運行n次，對於i = 2運行n-1次，...，對於i = n-1運行2次，並且對於i = n運行一次。平均而言，j循環將運行n/2次，所以該中間循環也被認爲是O（n）循環。當您將所有三個嵌套循環組合在一起時，總運行時複雜度爲O（n^3）。

來源

2014-09-29 16:06:16 chepner

漸近最差情況下的運行時間。需要一些說明

回答

相關問題