algorithm - 确定算法的确切执行次数

Question

我有算法，例如：

for(int i=1; i<=n; i++)
  for(int j=1; j<=2*n; j=j+2)
     for(int k=i; k<=j; k++)
        instr;

我需要找到一个公式来确定“instr”指令将被执行多少次。

我写了这个。. 但我得到的值不正确。例如对于 n=4，“instr”将被执行 43 次，但我的总和得到了 40。

我哪里搞砸了？

标签： algorithmmathtime-complexitycomplexity-theorycode-complexity

Answer 1

从代码

int count = 0;
for(int i=1; i<=n; i++)
  for(int j=1; j<=2*n; j=j+2)
     for(int k=i; k<=j; k++)
         count++;

可以将其转换为语义等价的：

int count = 0;
for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
        for(int k=i; k<=2*j - 1; k++)
           count++;

如果要count在两个代码版本的末尾打印变量，其值将是：

       |  loop 1 | loop 2
________________________________ 
N = 1  |    1    |   1
N = 2  |    6    |   6
N = 3  |    19   |   19 
N = 4  |    43   |   43 
N = 5  |    82   |   82

从第二个循环中，您提取了公式：

这在纸上是有道理的，但是，有一个问题。将公式转换为代码：

   public static int third_loop(int n ){
        int count = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                count += (2 * j - 1)  - i + 1;
        return count;
    }

并显示变量的值count：

       | loop  1 | loop 2 | loop 3
____________________________________
N = 1  |    1    |   1    |    1
N = 2  |    6    |   6    |    6
N = 3  |    19   |   19   |    18
N = 4  |    43   |   43   |    40 
N = 5  |    82   |   82   |    75

现在的count值不同了，原因是存在迭代，其中 (2 * j - 1) < i + 1，因此公式 (2 * j - 1) - i + 1 将产生负面结果，并且将这些结果添加到变量count中。在第二个循环中隐含地避免了一些事情。如果将第三个循环更改为：

  public static int fourth_loop(int n ){
        int count = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                count += Math.max((2 * j - 1)  - i + 1, 0);
        return count;
    }

一个会得到：

      | loop  1 | loop 2  | loop 3  | loop 4
__________________________________________
N = 1  |    1    |   1    |    1    |  1
N = 2  |    6    |   6    |    6    |  6
N = 3  |    19   |   19   |    18   |  19
N = 4  |    43   |   43   |    40   |  43
N = 5  |    82   |   82   |    75   |  82

所以你的公式的问题是它也考虑了负值，而你的代码没有。因为，我没有数学工具来给你精确的公式，所以我请你的来自math.stackexchange的朋友这样做。

编辑：从我提供的赏金中，马修塔得出了以下确切的表达：