确定算法的确切执行次数

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 次。

我哪里搞砸了？

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 的朋友这样做。

编辑： 从我提供的赏金中，Matthew Towers 得出以下精确表达式：

确定算法的确切执行次数

Determining the exact number of executions of an algorithm

algorithm

math

complexity-theory

time-complexity

code-complexity