該代碼的複雜性是什麼？

-1

我正在查看此鏈接上的代碼：
http://codeforces.com/contest/459/submission/7495216
該代碼是給定有向加權圖並希望找到具有嚴格遞增邊的最長路徑。
任何人都可以幫助我嗎？該代碼的複雜性是什麼？

#include <iostream> 
#include <vector> 
using namespace std; 
const int MAX = 300005; 
vector<pair<int, int> > w[MAX]; 
int dp[MAX], tmp[MAX]; 
int main() 
{ 
    ios::sync_with_stdio(false); 
    int n, m; 
    cin >> n >> m; 
    for (int i = 0; i < m; i++) 
    { 
     int u, v, len; 
     cin >> u >> v >> len; 
     w[len].push_back(make_pair(u, v)); 
    } 
    for (int i = 0; i < MAX; i++) 
    { 
     for (int j = 0; j < w[i].size(); j++) 
     { 
      int u = w[i][j].first, v = w[i][j].second; 
      tmp[v] = 0; 
     } 
     for (int j = 0; j < w[i].size(); j++) 
     { 
      int u = w[i][j].first, v = w[i][j].second; 
      tmp[v] = max(tmp[v], dp[u] + 1); 
     } 
     for (int j = 0; j < w[i].size(); j++) 
     { 
      int u = w[i][j].first, v = w[i][j].second; 
      dp[v] = max(dp[v], tmp[v]); 
     } 
    } 
    int ans = 0; 
    for (int i = 1; i <= n; i++) 
     ans = max(ans, dp[i]); 
    cout << ans << endl; 
    return 0; 
}

來源

2016-01-27 math.

對於那些投票結束的人：我不認爲這個問題太寬泛。計算函數的複雜度非常窄。近距離投票並不是一個超級低投票。 –

@VincentSavard對於任何需要解釋如何確定算法複雜性的人來說，這個問答都會變得有用。我認爲這太寬泛了。作者沒有給出關於一般問題的足夠狹窄的問題。 – typ1232

@ typ1231這可能會讓你覺得無聊，那麼它不適合我 –

對於每個節點，此代碼在所有傳出邊緣上進行迭代。所以運行時複雜度爲O（n * m），其中n是節點數量，m是數字邊緣。

編輯：仔細看看數據和代碼後，我說複雜度是O（n + m）。第一個和第二個循環遍歷所有邊，所以O（m）和第三個循環遍歷所有節點，所以O（n）。

來源

2016-01-27 22:22:20 FLUXparticle

該代碼的作者說它是O（n + m * log（m）） –

仔細看看代碼後，它是O（n + m ），因爲第二個循環只遍歷所有邊。我會糾正我的答案，但我沒有看到m * log（m）的原因。沒有涉及比較排序。他正在使用具有O（m）複雜度的桶排序。 – FLUXparticle

該代碼的複雜性是什麼？

回答

相關問題