时间戳

首页 > 解决方案 > 展开“m”相关循环

loops - 展开“m”相关循环

问题描述

考虑我有以下嵌套for-loops：

for(i1=1 to n)
   for(i2=1 to i1)
       for(i3=1 to i2)
           for(i4=1 to i3)
               for(i5=1 to i4)
                   count++;

会增加多少倍count？

如果有 'm' 个这样的依赖循环，我们如何计算 count 变量的值？

标签： loopstime-complexity

解决方案

您可以尝试一些数字并得到答案。（在您的示例中，m = 5您将1,6,21,56,126获得nequal 1,2,3,4,5）

提示- 它将是Binomial coefficients C(n,5)（您可以使用The On-Line Encyclopedia of Integer Sequences找到这个）

所以对于m嵌套循环，你将得到count等于C(n+m-1,m)-> 因为 minimum 是选择m元素，所以mm 的二项式系数中的第一个元素是 0 - 你可以在这里了解更多信息。

为什么这是答案？它实际上是数学问题-但简单的解释：检查Pascal's triangle-它是数字之间的差异之和-您的情况，每个循环取两个较高的总和-在您的循环中，每个循环都执行到较高的索引-相同的方法

推荐阅读