該算法的運行時間

我有這個算法，我不知道它的時間複雜度是什麼。在該算法的運行時間

int oc(int n) { 
    if (n == 0) 
    { 
     return 0; 
    } 
    int s = p[n][0]; 
    for (int i = n-1; i > 0; i--) 
    { 
     int a = p[n][i] + oc(i); 
     if (s > a) 
     { 
      s = a; 

     } 
    } 
    return s; 
}

我假設有（N-1）迭代的for循環，但可以弄清楚什麼是總運行時間使用遞歸的時候。

來源

2016-11-09 Pierre P.

（這是一個_procedure_。要做一個_algorithm_，程序必須解決問題。） – greybeard

讓T(n)是計算oc(n)的複雜性。由於用於計算oc(n)您從n-1運行for循環1和遞歸調用oc(i)，因此

T(n)=T(n-1)+T(n-2)+...+T(1) (*).

相反，如果在T（N-1）我們把

T(n-1)=T(n-2)+T(n-3)+...+T(1)

在(*)平等我們將得到：

T(n)=2*(T(n-2)+...+T(1))

如果我們繼續同迭代T(n-2)，T(n-3)等。我們將結束下列等式：

T(n)=2*(T(n-2)+...+T(1)) 
=4*(T(n-3)+...+T(1)) 
=2^i*(T(n-i-1)+...+T(1)) 
=2^n*T(1)/2=O(2^n).

這種複雜性的原因是 - 你的算法計算同樣的事情很多次。如果您記住已計算oc函數值的數組中的值，並在函數的第一部分中添加一個檢查，該函數將直接從數組中返回值（如果已計算），而不是運行循環，然後再次執行同樣的工作，你算法的複雜性將會急劇變化，並且將會是O(n)，因爲算法會在你的循環第一次迭代時計算所有的值並存儲。

來源

2016-11-09 23:57:25 simon

謝謝你的回答！使用記憶法最多能達到O（n）時間複雜度的適當算法是什麼？ –

@PierrePasquet記憶技術非常易於使用，並且您的算法非常適合，您只需要在oc函數中引入2個數組並將它們作爲參數傳遞給oc：memo_oc int []和flag_oc bool []。 Init flag_oc帶有錯誤值，即，我們沒有任何記憶/計算的oc值用於重用。設置flag_oc [0] = true和memo_oc [0] = 0。將if（n == 0）{...}條件替換爲if（flag_oc [n]）{return memo_oc [n];}並插入「flag_oc [n] = true; memo_oc [n] = s;」「return s;」之前的代碼行 – simon

它是O（2 ⁿ）。見迭代次數如何增加ň積聚：

n | f(n) = total iterations 
---+------------------------------------------------- 
1 | 0 
2 | 1 + f(1) = 1 + 0 = 1 
3 | 2 + f(2) + f(1) = 1 + 2f(2) = 1 + 2.1 = 3 
4 | 3 + f(3) + f(2) + f(1) = 1 + 2f(3) = 1 + 2.3 = 7 
...| ... 
n | .... 1 + 2.f(n-1) = 2^(n-1) - 1

來源

2016-11-09 23:49:01 trincot

該算法的運行時間

回答

相關問題