许多算法的循环如下：
for a from 1 to n
for b from 1 to a
for c from 1 to b
for d from 1 to c
for e from 1 to d
...
// Do O(1) work
换句话说，循环嵌套的深度是k层，外层循环从1到n，内层循环从1到上面的索引例如，这在代码中显示，用于遍历数组中所有位置的k元组。
假设k是固定的，那么这个代码的运行时间总是（nk）吗？对于n=1的特殊情况，功是Θ（n），因为它只是数组上的一个标准循环；对于n=2的情况，功是Θ（n2），因为内环所做的功是由
0+1+2+…+n-1=n（n-1）/2=Θ（n2）
当k变大时这种模式会继续吗还是只是巧合？
最佳答案
是的，时间复杂度为（nk）。衡量这个代码的复杂性的一种方法是看它产生什么值。一个特别有用的观察结果是，这些循环将迭代数组{1，2，3，…，n}的所有可能的k元素子集，并花费o（1）时间生成其中的每一个。因此，我们可以说运行时是由这样的子集的数量给出的。给定一个n元集，k元子集的个数是n choose k，它等于
n！/k！（n-k）！
这是由
n（n-1）（n-2）……（n-k+1）/k！
这个值肯定不大于这个值：
N·N·N·……·不适用（附N份K份）
=nk/k！
这个表达式是o（nk），因为1/k！项是一个固定常数。
同样，当n-k+1≥n/2时，此表达式大于或等于
（n/2）·（n/2）··（N/2）/K！（附N/2的K份副本）
=nk/k2K
这是Ω（nk），从1/k开始！2k是一个固定常数。
由于运行时是o（nk）和Ω（nk），因此运行时是_（nk）。
希望这有帮助！
关于algorithm - 在k层深循环嵌套中进行迭代的时间复杂度始终为Θ(nᵏ)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19719441/