根据 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：无限

第2个内循环执行时j=log2(n)。由于它小于 n，因此永远不会满足条件，最终成为无限循环。

Answer 2

由于 i 开始时小于 n 并且第一个 for 循环使 j 达到 i，然后第二个 for 循环是无限的。第二次循环需要把循环条件改成k <= n否则就是无意义的程序

根据 n 执行语句的次数

number of times a statement gets executed in terms of n

java

big-o

analytics