algorithm - 计算一段代码的时间效率

Question

我有这段代码:

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 作为参数给出。

到目前为止我已经计算了这个:

main for循环呈指数递增，也就是说它的时间效率是O(log m)

第一个for循环消耗常数时间O(200)，所以不影响代码的时间效率。

第二个for循环每次迭代递减n个值的1/2，因此它的时间效率是O(log n)

第三个循环每次迭代递增 3 => 它具有 O(m/3) 时间效率，但我们不需要常量，所以它是 O(m )

总而言之，当我们组合所有内容时，我们得到 O(log(m) * (log n + m))。

这个分析都正确吗？

Answer 1

使用 Sigma 表示法，您可以有条不紊地发现: