嵌套循环与依赖边界的迭代次数

Question

出于好奇，我尝试做了以下操作，但对我来说并不是那么显然； 假设我有嵌套循环与运行时边界，例如：

 t = 0 //  trip count
 for l in 0:N
   for k in 0:N
     for j in max(l,k):N
        for i in k:j+1
           t += 1

 t is loop trip count

是否有一种通用的算法/方法（显然比N^4更好）来计算循环行程次数？

如果没有，我很想知道您如何处理这个特定的循环。上面的循环是对称的（它循环遍历对称的四阶张量），我还对检测循环对称性的方法感兴趣。

我假设迭代边界仅取决于常数或先前的循环变量。如果您知道链接/期刊文章，那就太好了。

- Anycorn

---

你试图实现什么并不明显 - 你能否先从问题开始，而不是解决方案？ - Eli Bendersky

@aaa：最后一个循环可以用t += j + 1 - k或类似的东西来替换，但我仍然不知道你想做什么。 - Eli Bendersky

@Eli 统计内部循环执行的次数，而不实际运行循环。 - Anycorn

@aaa：有什么一般性的方法吗？我的意思是它可以变得多么通用？ - Unreason

Answer 1

我相信内部循环会运行

t = 1/8 * (N^4 + 6 * N^3 + 7 * N^2 + 2 * N)

次数。

我并没有直接解决问题，而是对从1到50的N精确计算t拟合了一个四阶多项式表达式，希望能得到精确匹配。

为了计算精确的t值，我使用了

sum(sum(sum(sum(1,i,k,j+1),j,max(l,k),N),k,1,N),l,1,N)

这应该等同于实际运行您的循环。

数据拟合，对数比例 http://img714.imageshack.us/img714/2313/plot3.png

N从1到50的拟合完全匹配，并使用两种方法计算N=100得到13258775。

编辑： 这个练习是使用开源代数系统maxima完成的，这里是实际源代码（输出被丢弃）：

nr(n):=sum(sum(sum(sum(1,i,k,j+1),j,max(l,k),n),k,1,n),l,1,n);
M : genmatrix( lambda([i,j],if j=1 then i else nr(i)), 50, 2 );
coefs : lsquares_estimates(M, [x,y], y = A*x^4+B*x^3+C*x^2+D*x+E, [A,B,C,D,E]);
sol(x):=ev(A*x^4+B*x^3+C*x^2+D*x+E, coefs);
sol(N);
S : genmatrix( lambda([i,j], if j=1 then i else sol(i)), 50, 2);
M-S;
plot2d([[discrete,makelist([M[N][1],M[N][2]],N,1,50)], sol(N)], [N, 1, 60], [style, points, lines], [color, red, blue], [legend, "simulation", sol(N)], [logy]);
compare(nr(100),sol(100));

- Unreason

Answer 2

如果你想知道内部循环执行了多少次：

for j in max(l,k):N

将被执行，只需计算：N - max(l, k) 假设是开区间，N + 1 - max(l, k) 假设是闭区间。

例如，如果：

l = 2
k = 7
N = 10

那么它将在7、8、9、10（闭区间）上运行，因此确实会运行10 + 1 - 7 = 4次。

- Eli Bendersky

---

我对找出整个i、j、k、l循环执行的次数很感兴趣，而不仅仅是单个循环。 - Anycorn

我认为他想要一个t的最终值的公式，而不是实际循环。 - IVlad

Answer 3

答案是不，只要循环边界可以以任意方式依赖于外部变量，这将提供获得积分级数闭式公式的通用方法。

为了看清楚这一点，请考虑以下内容：

for x in 0:N
  for y in 0:f(x)
    t += 1

旅行次数t(N)等于总和t(N)=f(0)+f(1)+f(2)+f(3)+...+f(N-1)。

因此，如果您可以获得t(N)的闭式公式，而不考虑f()，那么您已经找到了一种非常通用的产生闭式公式的方法，我会说太通用了，因为这里对应一个积分，而众所周知，并非所有积分都有闭式公式。

- Antti Huima