时间迭代的k层深的循环嵌套总是Θ（nᵏ）的复杂性？ [英] Time complexity of iterating over a k-layer deep loop nest always Θ(nᵏ)?

问题描述

许多算法中都有循环，即是这样的：

Many algorithms have loops in them that look like this:

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到其上方的索引。这说明了，例如，在code遍历所有k元组位置的数组中。

In other words, the loop nest is k layers deep, the outer layer loops from 1 to n, and each inner layer loops up from 1 to the index above it. This shows up, for example, in code to iterate over all k-tuples of positions inside an array.

假设K是固定的，是这个code运行时始终与西塔（N ^K ）？对于特殊情况，其中n = 1，工作​​和西塔（N），因为它只是一个标准的遍历数组，并为当n = 2的工作和西塔（N ² ）因为内环所做的工作是给

Assuming that k is fixed, is the runtime of this code always Θ(n^k)? For the special case where n = 1, the work is Θ(n) because it's just a standard loop over an array, and for the case where n = 2 the work is Θ(n²) because the work done by the inner loop is given by

0 + 1 + 2 + ... + N-1 = N（N-1）/ 2 =＆的Theta;（正 ² ）

0 + 1 + 2 + ... + n-1 = n(n-1)/2 = Θ(n²)

请问这种模式继续当k变大？还是只是一个巧合吗？

Does this pattern continue when k gets large? Or is it just a coincidence?

推荐答案

是的，时间复杂度将与西塔（N ^K ）。衡量这个code复杂性的方法之一是看什么样的价值观它产生。一种特别有用的观察是，这些环将遍历数组{1，2，3，...，n}的所有可能的K-元素子集和将花费O（1）时间产生其中的每一个。因此，我们可以说，运行时被这种子集的数量给定。给定的n元组：K-元件子集为n选择k的数量，这是等于

Yes, the time complexity will be Θ(n^k). One way to measure the complexity of this code is to look at what values it generates. One particularly useful observation is that these loops will iterate over all possible k-element subsets of the array {1, 2, 3, ..., n} and will spend O(1) time producing each one of them. Therefore, we can say that the runtime is given by the number of such subsets. Given an n-element set, the number of k-element subsets is n choose k, which is equal to

N！ / K（N - K）！

n! / k!(n - k)!

这是由下式给出

N（N-1）（N-2）......！（N - K + 1）/ K

n (n-1)(n-2) ... (n - k + 1) / k!

这个值比这个肯定没有更大的：

This value is certainly no greater than this one:

N'middot; N'middot; N'middot; ...＆middot; N / K！ （其中n k个拷贝）

n · n · n · ... · n / k! (with k copies of n)

= N ^K / K！

这EX pression是O（n ^K ），因为1 / K！术语是固定不变的。

This expression is O(n^k), since the 1/k! term is a fixed constant.

同样地，当n - K + 1＆格; n / 2个，这当然pression大于或等于

Similarly, when n - k + 1 ≥ n / 2, this expression is greater than or equal to

（π/ 2）＆middot; （N / 2）＆middot; ...＆middot; （N / 2）/ K！ （其中n k个拷贝/ 2）

(n / 2) · (n / 2) · ... · (n / 2) / k! (with k copies of n/2)

= N ^K / K！ 2 ^K

= n^k / k! 2^k

这是与欧米茄（N ^K ），自1998年1 / K！ 2 ^K 是固定不变的。

This is Ω(n^k), since 1 / k! 2^k is a fixed constant.

由于运行时间为O（n ^K ）和欧米茄（N ^K ），在运行时和西塔（N ^K ）

Since the runtime is O(n^k) and Ω(n^k), the runtime is Θ(n^k).

希望这有助于！

这篇关于时间迭代的k层深的循环嵌套总是Θ（nᵏ）的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！