java - 语句执行的次数(以 n 为单位)

Question

我想要真正的方法来获取代码中语句的执行次数(以 n 为单位)。

例如:在此代码中，MyStatement1 和 MyStatement2 执行了多少次，为什么？

sum = 0;
for (i=1; i<=n; i*=2) {
    for (j=1; j<=i; j++) {
        sum++; // MyStatement1
    }

    for (k=1; j<=n; k++) {
        sum++; // MyStatement2
    }
}

Answer 1

MyStatement1:O(n)

精确的执行次数基于 geometrical progression 的总和。外循环将执行 m 次，其中 2^m = n 因此 m = log2(n)

内部循环将执行1 + 2 + 4 +... + 2^m次。这是几何级数的总和:

(1-2^m)/(1-2) = O(2^m) = O(2^log2(n)) = O(n)

MyStatement2:无穷大

执行第二个内部循环时j=log2(n)。由于该值小于 n，因此永远不会满足条件，从而导致无限循环。