算法時間複雜度分析（三個嵌套for循環）

下面是我簡要介紹的代碼。這兩個for循環應該有O(n2) where n=vertices的複雜性。我只是無法弄清楚外部for循環的整體時間複雜度。我認爲它會是O(E * n2) where E is the number of edges and n is the number of vertices。算法時間複雜度分析（三個嵌套for循環）

int vertices; 

for(int Edges = 0; Edges < vertices-1 ; Edge++) 
{ 
    for (int i=0; i< vertices; i++) 
     for (int j=0; j<vertices; j++) 
     { 
      // TASKS 
     } 
}

此代碼適用於prim算法。如果你願意，我可以發佈整個代碼。謝謝:)

來源

2014-12-06 user3490561

啊!!!這是什麼典型的！

在你的內部循環中，你有變量名爲i & j，所以你很容易找出複雜性。

只是增加了一個EDGE變量，它與其他2沒有任何區別，因此您會感到困惑！檢查迭代次數！

外循環將運行VERTICES-1迭代。因此，複雜性=（VERTICES-1）*（VERTICES）*（VERTICES）=（VERTICES^3） - （VERTICES^2）。

程序的複雜性是O（頂點^ 3）或爲O（n^3），其中n =頂點...

來源

2014-12-06 11:58:11

應該沒有吧是O（E * n2）其中E是邊的數量，n是頂點的數量？對不起，先生我是一個初學者 – user3490561 2014-12-06 11:59:38

@ user3490561- nO，迭代的總次數將指導複雜性。你可以說它正在運行O（n^2 * E），但是E本身從0迭代到'VERTICES-1'迭代。並且，請重新回答我的答案。另外，我是一個像你一樣的學生，不是先生。請跟我冷靜一下。 – 2014-12-06 12:01:58

你的意思是說，常量被拋出，因此（VERTICES-1）變成（VERTICES）。因此，O（VERTICES * VERTICES * VERTICES）= O（頂點^ 3） – user3490561 2014-12-06 12:11:29

西格瑪符號使事情變得清楚：

enter image description here

來源

2014-12-08 16:22:18

謝謝先生......非常感謝。 – user3490561 2014-12-08 18:17:51

不客氣。但是，如果您對總結不太熟悉，則可以使用此工具：http://www.combineditorix.com/ – 2014-12-08 20:50:00

算法時間複雜度分析（三個嵌套for循環）

回答

相關問題