C++數據結構大O

-2

數據結構中的Hello大O代碼計數爲（n^2 + N^2）忽略我們取最大的，還是隻有N^2，因爲DM處於同一個循環？謝謝。C++數據結構大O

int sum1,sum2; 
    for (int i = 0 ;i < n;i++) 
    { 
     for (int j = 0 ; j < n; j++) 
     { 
      sum1 = i + j; //DM 
      sum2 = i ; //DM 
     } 
    }

來源

2013-02-15 user1948105

這沒有意義。要麼你很高，要麼我很高。 – 2013-02-15 19:54:12

什麼是「N」？什麼是「DM」？算法就像O（n^2）一樣，它執行2 n^2個賦值和n^2加法。（這沒有提及程序的* runtime *，因爲一個聰明的編譯器可能會找出結果並將其存儲起來。） – 2013-02-15 19:54:16

我不高n表示未知的循環數...如果您不知道數據結構請不要回答，DM意味着數據移動，因爲在數據結構中它們被分成DM和DC數據比較 – user1948105 2013-02-15 19:56:25

它既是O（N^2）又是O（2 * N^2）。它也是O（1/2 * N^2）和O（1000 * N^2）。由於big-O符號爲defined，它們都是等效的。

來源

2013-02-15 19:58:23

是的，我確實知道，但我只是想知道在將它簡化爲N^2 + N^2或N^2之前我們如何看待它，因爲兩個dm都處於相同的循環中，而不是因爲大O忽略常量 – user1948105 2013-02-15 20:03:46

在簡化之前有很多方法可以查看它。我可以說我知道循環內的所有內容都是不變的，只需將其計爲'1'，或者我可以統計賦值，比較或整數運算的次數。重點在於大O，我選擇哪一個並不重要。 Big-O不是爲精確的性能比較而設計的，所以說O（2N^2）與O（N^2）是沒有意義的。對於真實世界的性能比較，最好的方法通常是僅對代碼進行基準測試。 – 2013-02-15 20:15:39

啊哈謝謝你清理它。 – user1948105 2013-02-15 20:18:44

ordo符號只考慮計算複雜度增長最快的部分，如果有加法和減法的話。常量也沒有記錄。所以這段代碼本質上運行在O[2 * (n^2)]（沒有優化 - 最好說它的時間複雜度就是這個那個），然後它就是O(n^2)。

來源

2013-02-15 19:55:41

謝謝，確切的運行時間是2 * n^2？ – user1948105 2013-02-15 19:59:04

@ user1948105誰知道確切的運行時間？ – 2013-02-15 19:59:24

C++數據結構大O

回答

相關問題