如何分析这种嵌套循环算法

Question

所以我从讲师那里得到了这个算法分析，我需要一些帮助，为什么外循环是n-1，不是应该是n-2吗？并且内环应该是log3(n(而不是log3(n(+1

for(int a=3; a<=n; a++)                 n+1-2 = n-1

for(int a=1; a<n; a=a*3)          log3 (n) +1
System.out.println(a);         log3 (n)

总计=(n-1(*(log3(n(+1+log3(n((

=(n-1)*(2 log3(n) + 1)
=2(n log3(n))+n -1 – 2 log3(n)
=n log3(n) + n – log3(n)

这是算法分析的正确答案吗？这就是我的讲师给我看的。有人能给我解释吗？

Answer 1

如果您想要对操作进行非常精确的计数，那么指定以下内容非常重要：您在计算哪些操作？增量a++的数量？比较次数a<=n？循环体的执行次数？

如果你没有指定你要计算的运算，那么担心额外的+1或-1就没有多大意义了。

注意，用作外循环的计数器的变量被称为a，用作内循环计数器的变量也称为a。虽然这在C++中是可以做到的，但我强烈建议不要这样做。这很令人困惑，也是一个很好的错误来源。

外循环将运行n-2次迭代。内部循环将运行ceil(log3(n((迭代(其中ceil是天花板函数(。行System.out.println(a)不是一个循环，它只是一行代码，所以你可以写"；1〃；如果你愿意的话；写作没有多大意义；log3(n("；在这里

因此，执行线路System.out.println(a)的总次数为：

(n-2(ceil(log3(n((。

您可能想要计算写入的确切字符数。再一次，我们回到了一个事实，你没有具体说明你在计算什么。字符数取决于a的确切值，因此它在循环的每次迭代中都会发生变化。但总的来说，每次调用System.out.println(a)都会打印大约log10(n(个字符，因为我们是用十进制编写的。