java - 对数等for循环转换为求和表示法

Question

我需要有关将 for 循环转换为求和国家的帮助。有些很容易，但有些则有点棘手。我需要正确设置求和符号。

像这样:(正确的例子循环)

举个例子:

for (int i = 0; i < n; i = i + 1)  
  a = i; //cost 1

求和 1，i=0 到 n-1 == n。

我需要以下方面的帮助:

对数(只是正确的求和符号)

for (int i = 0; i < n; i = 2 * i)  
  a = i; //cost 1

求和 1，i=0 到 log(n)-1 == log n。对吗？？

三重嵌套(求和符号和一步一步为什么它最终会这样)

for (int i = 0; i < n; i = i + 1)  
for (int j = 0; j <= i; j = j + 1)  
for (int k = 0; k <= j; k = k + 1)  
  a=i; //cost 1

Answer 1

三重嵌套循环

我将提供一个简单但非常有用的方法来根据渐近符号来分析此类求和。

这是一个非常通用的方法，你可以用它来绑定(bind)许多多个索引求和而不需要很大的努力。

上限

首先，让我们推导出总和的上限。这很容易:

下界

本例中的技巧是导出下限。经验法则是减少求和范围，将较低的求和索引递增到较高索引的分数，然后在嵌套循环中将新的较低索引替换为较高索引。这也很简单:

把它放在一起

从这两个不等式，你可以推断出:

根据渐近分析给出:

如您所见，您的三重嵌套循环具有与以下相同的渐近时间复杂度:

for(int i = 0; i < n; i = i + 1)  
   for(int j = 0; j < n; j = j + 1)  
      for(int k = 0; k < n; k = k + 1)  
         //operations of cost 1