计算的代码

组块的时间效率我有这样的块的代码：计算的代码

int f = 0; 

for(int i=1 ; i<m ; i=i*2) { 
    for(int l=500 ; l<700 ; l++) { 
     f++; 
    } 
    for(int j=n ; j>0 ; j=j/2) { 
     f++; 
    } 
    for(int k=0 ; k<m ; k=k+3) { 
     f++; 
    } 

    f += 10; 
}

其中m和n给定为参数。

到目前为止，我已经计算出这一点：

主要用于成倍周期为增量，这意味着它的时间效率O(log m)

，第一对循环消耗一定的时间O(200)，因此它不会影响时间代码的效率。

第二个用于循环递减由具有n个每itteration的值的1/2，因此，其时间效率是O(log n)

由3每itteration第三对周期为增量=>它具有O(m/3)时间效率，但我们不需要一个常数，所以它是O(m)

总而言之，当我们结合一切时，我们得到了O(log(m) * (log n + m))。

这个分析全部正确吗？

来源

2014-11-08 Mark

@ ChrisJester-杨n和m是参数，因此不能进一步简化如你所建议的。对于两个变量，big-O的定义是“如果存在M，N，C，则运行时间为O（f（n，m）），使得对于所有m> M，对于所有n> N，运行时间<= Cf（n，m）“。 – 2014-11-09 01:56:55

@anonymous有道理。在那种情况下，OP的分析似乎是正确的。 – 2014-11-09 01:59:51

使用西格玛符号，可能会发现有条不紊：

enter image description here

来源

2014-11-09 13:59:30

回答

相关问题