按操作顺序总共打印了多少颗星星

Question

序列

总共打印了多少颗星星运营数量：

A a = new A(); for (int i=0; i<N; ++i) a.f(N);

class A
{
  int k = 0;
  void f(int N)
  {
    if (k == 0)
    {
      k = N;
      for (int i = 0; i<N; ++i) StdOut.print("*");
    }
      k = k-1;
      StdOut.print("*");
  }
}

这个问题的答案不是O（n）吗？我不确定为什么，但这似乎适合我 - 当我查看代码时。似乎方法 f 中的 for 循环仅在第一次调用 a.F（N） 时运行，因为 if 语句 if（k == 0） - 如果第一个 for 循环是：for （int i=0; i <= N; ++i） 那么答案将是 O（n^2），我想。

Answer 1

实际上，该方法的for循环仅在第一次调用时运行并打印 N 个星号。每个调用（也是第一个）也打印一个星号，因此星号的总和为 2N，即 O（n）。

如果顶部循环一直运行到包含 N，那么 k 在最后一个额外的调用处将为 0，因此它就像第一次调用一样：打印 N 个额外的星号，加上为任何调用打印的星号。

这使得 3N+1 成为星号，仍然是 O（n）。

片段 （JavaScript）

var N = 200;
var a = new A(); 
for (var i=0; i<N; ++i) a.f(N);
console.log('asterisks: ', a.count);
function A() {
  var k = 0;
  this.count = 0; 
  this.f = function(N)
  {
    if (k == 0)
    {
      k = N;
      for (var i = 0; i<N; ++i) this.count++;
    }
    k = k-1;
    this.count++;
  };
}

当 N=200 时，输出为 400。