为什么这个算法的bigO m^2 * n？

我想确定为什么这个算法的bigO是m^2 * n，以及为什么最内层循环在m^2 * n步骤中执行。为什么这个算法的bigO m^2 * n？

int m=10, n=15; 
    int inLoop = 0, midLoop = 0, outLoop = 0; 

    for(int i=1;i<=m;i++) 
    { 
    outLoop++; 
     for(int j=1;j<=2*i-1;j++) 
     { 
      midLoop++; 
      for(int k=1;k<=n;k++) 
      { 
      inLoop++; 
      } 
     } 
    } 

    System.out.println("Out Loop " + outLoop); 
    System.out.println("Mid Loop " + midLoop); 
    System.out.println("Inner Loop " + inLoop);

当我运行这个时，我得到内循环运行1500次，中间循环100次，最外层循环10次。

运行此代码之前我认为这代码跑第一环路米倍，第二环路平方公尺倍，最后循环Ñ倍，这与这些值将导致内循环输出为15,000。

显然，算法似乎是执行最内层循环中平方公尺* n个步骤而不是在立方公尺* n个步骤我相信这将是。

来源

2014-09-29 mufc

为什么中间循环会运行m^2次？ – Compass 2014-09-29 19:39:32

（2i-1）当你解决这个问题（这是一个总结）结果是相等的m^2次。 @Compass – mufc 2014-09-29 19:40:53

_在运行这段代码之前，我认为这段代码运行了第一个循环m次，第二个循环运行了m^2次，最后一个循环运行了n次_第二个循环或者这一行中的最后一个循环都不正确。要么是最后一个循环的m^2 * n，要么是第二个循环的另一个m。 – Compass 2014-09-29 19:45:47

求和（2I - 1）I开始为1，并且在m结束是：

2 *求和（ⅰ） - 求和（1）= 2 *（M + 1）/ 2 * M - 米= O（平方公尺）

这仅仅是为了在外部和中间环

内环是直线前进，导致O（n * m个^ 2）

来源

2014-09-29 19:46:45 Keeto

所以m^2是用于外部和中间循环？我认为外部循环运行了m次，然后中间循环运行m^2，所以我必须乘以它们才能得到m^3 * n。你能再解释一下吗？ @Keeto – mufc 2014-09-29 19:49:37

外循环运行m次，每次外循环运行时，中循环运行（2 * i-1）次，其中i是外循环的迭代次数。 – Keeto 2014-09-29 23:07:35

AHHHH！谢谢。现在完美。 – mufc 2014-09-30 01:09:32

我认为想法是清楚的是，你要指望每个循环重复的频率，而不是细节不清楚。现在，为了缓解这些事情，你可以分开这些循环并单独征服它们。

对于最外层的循环，很明显它运行的是m次。也就是说，它的复杂性是Θ（m x），其中x是里面内容的复杂性。对于最内层的循环来说，情况也很简单，它只取决于n的值，它是不变的，所以它的复杂度是Θ（n）。

中间循环是一个有点复杂。它的复杂性取决于i，但i不是常量而是外部循环的循环变量。但是，您可以使用平均值作为替换。在这种情况下，平均数非常简单，如果您绘制一张检查牌，您可以看到它。在外循环的第一次迭代中，i=1，所以j将只取一个值1。在第二次迭代中，i=2和j=1..3。第三，它是j=1..5等等。如果你将它们放在彼此的下面，你会得到一个三角形的形状。它的顶部宽度为1，底部宽度为2m-1，高度为m。因此，该地区是((2m-1)+1)/2=m。

把此一起，必须复杂Θ（M），用于所述外层和中间环和Θ（n）的用于内循环，使得它Θ（米² n）的整体。

来源

2014-09-29 20:11:58

如果你只是运行我从上面得到的代码，你会看到中间的循环输出100次，所以我不明白它是如何成为阶m的，当它是100时，m是10。它不能是m – mufc 2014-09-29 20:35:55

将外部循环的十个乘以内部循环的平均十个并且您得到您的一百个。也许它不够清楚，但重点是尽可能分开处理每个循环。 – 2014-09-30 18:32:02

为什么这个算法的bigO m^2 * n？

回答

相关问题