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

回答

相关问题