通过数组的所有可能序列进行迭代的时间复杂度是多少？

Question

遍历数组内所有可能的索引序列的算法。

一个循环的时间复杂度是线性的，两个嵌套循环的时间复杂度是二次O（n ^ 2）。但是，如果嵌套另一个循环并遍历这两个索引之间分隔的所有索引怎么办？时间复杂度是否上升到三次O（n ^ 3）？当N变得非常大时，似乎没有足够的迭代来考虑三次方的复杂性，但似乎是二次O（n ^ 2）

这是考虑N =数组长度的算法

for(int i=0; i < N; i++)
{
    for(int j=i; j < N; j++)
    {
        for(int start=i; start <= j; start++)
        {
          //statement
        }
    }
}

这是N = 7（直到i = 7时）的迭代的简单视图：

等等..

我们应该将时间复杂度视为二次，三次还是不同的大小复杂度？

Answer 1

对于基本

for (int i = 0; i < N; i++) {
    for (int j = i; j < N; j++) {
        // something
    }
}

我们执行something n * (n+1) / 2时间=> O(n^2)。至于原因：这是的简化形式
sum (sum 1 from y=x to n) from x=1 to n。

对于您的新案例，我们有一个类似的公式：
sum (sum (sum 1 from z=x to y) from y=x to n) from x=1 to n。结果是n * (n + 1) * (n + 2) / 6=> O(n^3)=>时间复杂度是三次。

将1在这两个公式是你进入的成本something。特别是在您进一步扩展公式的地方。

请注意，所有索引可能相距一个，我没有特别注意<vs <=等。

Answer 2

简短的回答，O(choose(N+k, N))与 相同O(choose(N+k, k))。

这是如何到达那里的长答案。

您的基本问题版本正确。使用k嵌套循环，您的复杂性将达到O(N^k)无穷N大。然而，随着k两者N的变化，行为更加复杂。

让我们考虑一下相反的极端。假设它N是固定的，并且k是变化的。如果N是 0，则您的时间是恒定的，因为最外层循环在第一次迭代时失败。如果N = 1那么您的时间是O(k)因为您只用一个选择遍历所有嵌套级别，并且每次只有一个选择。如果N = 2发生更有趣的事情，你就会一遍又一遍地进行嵌套，这需要时间O(k^N)。一般来说，固定N时间是由于遍历嵌套所花费O(k^N)的时间以及序列前进的位置所花费的时间之一。这是意想不到的对称！kO(k^(N-1))

k如果和N都很大会发生什么？其时间复杂度是多少？这里有一些可以给你直觉的东西。

我们可以描述到达最内层循环的所有时间吗？是的！考虑一下k+N-1槽位，k其中一些是“再进入一个循环”，N-1一些是“我们将索引前进了 1”。 我断言如下：

1. 这些与我们到达最内层循环的决策序列一一对应。通过查看哪些指数比其他指数大以及大多少就可以看出。
2. 最后的“进入另一个循环”条目是进入本次迭代的最内层循环所需的工作，不会导致任何其他循环迭代。
3. 如果1 < N我们真的需要更多的独特工作才能到达终点。

现在这看起来一团糟，但有一个技巧可以出乎意料地简化它。

诀窍是这样的。假设我们采用这些模式之一，并在最后的“再进入一个循环”条目的最后一段中的某处插入一个额外的“我们将索引前进 1”。有多少种方法可以做到这一点？答案是，我们可以在最后一段的任意两个点之间插入最后一个条目，包括开始和结束，并且除了条目之外还有一种方法可以做到这一点。换句话说，实现这一目标的方法数量与本次迭代中的独特工作量相匹配！

这意味着总工作量O(choose(N+k, N))也与 成正比O(choose(N+k, k))。

值得知道的是，从正态近似到二项式公式，如果N = k事实证明这O(2^(N+k)/sqrt(N+k))确实比多项式增长得更快。如果您需要更一般或更精确的近似，您可以对 中的阶乘使用斯特林近似choose(N+k, N) = (N+k)! / ( N! k! )。