arrays - 不断降低的数组​​迭代复杂度

Question

所以我有点不确定真正称这个时间复杂度是什么(我认为它是 O(N^2)，但我不确定我是否可以这样调用它)

void solve(int[] nums, int k){
 int len = nums.length; 
  while(len > 0){ 
   for(int i = 0; i < len; i++){ System.out.println("hello"); }
   len-=k;
  }
}

所以我意识到它是:n + n-k + n-2k + n-3k + ...我知道我不会在每次迭代中将搜索空间减半，所以显然不是 n*log(n)，其中 n 是数组的大小。我确实意识到它类似于发散级数 (1+2+3+4+...); 因此，我之前的假设是 O(N^2) == n (n+1)/2，但我真的可以这么调用它吗？谢谢。

Answer 1

直觉上，我们应该期望它类似于Θ(n²/k + n)。如果您将每个工作单元想象成一个正方形，您可以想象我们正在用这些正方形构建一个三角形。每列代表外循环的一次迭代。三角形的高度是 n，三角形的宽度是 (n/k)，所以我们期待这样的结果出现。例如，如果 k = 1 且 n = 5，则三角形如下所示:

*
**
***
****
*****

如果 k = 2 且 n = 6，则三角形如下所示:

*
*
**
**
***
***

其中的 n 项是必要的，因为如果我们允许 k 变得非常非常大，我们仍然总是至少进行一次循环迭代，因此我们不希望我们的运行时间降为零。

现在，让我们看看数学是否与我们一致。正如您提到的，您正在查看总和

n + (n - k) + (n - 2k) + (n - 3k) + ... + (n - (n/k)k).

这里共有 (n/k) + 1 个 n 项的副本，因此我们可以将事物重新组合为

n((n / k) + 1) - (k + 2k + 3k + ... + (n/k)k).

然后我们可以分解出第k项得到

n((n / k) + 1) - k(1 + 2 + 3 + ... + (n / k)).

第二项是高斯著名的止于 (n/k) 的求和，计算结果为

n((n / k) + 1) - (n / k)((n / k) + 1) / 2.

分解出一个 ((n/k) + 1) 项给我们

((n / k) + 1)(n - n / 2k)

如果我们现在将所有内容相乘，我们得到

n(n / k) - n² / 2k² + n - n / 2k

= 2n²k / 2k² - n² / 2k² + n - n / 2k

= (2n²k - n²) / (2k²) + n - n / 2k

= Θ(n² / k + n).

所以数学与我们的直觉相符。