java - 复杂性分析

Question

我试图计算这种复杂性，但我做不到

我以为这将是一个无限循环，但我的导师把这个问题作为作业给了我，并要求我找出复杂性以及 statement1 & statement2 将执行多少时间。

谁能帮我 ？

   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

当他谈论复杂性时，如果他指的是分支的数量（圈），我想它是 3 还是 6，这取决于他是否计算隐含的“If”测试来结束 for 循环（我不记得了，但我认为应该是 6）。

至于语句的执行次数，必须以n的初始值为准。看起来 n=1 执行第一个语句一次并跳过第二个语句，但是对于其他正值——嗯——跟踪它，看看会发生什么。

有时玩“电脑”并在一张纸上写下 N、J、K、I 的值会有所帮助。