什么是迭代的时间复杂度通过阵列的所有可能序列

丹尼蜜蜂:

一种算法,通过索引的阵列内的所有可能的序列前进。

时间单个环路的复杂性,并是线性的和两个嵌套循环是二次为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):

在这里输入图像描述 在这里输入图像描述

等等..

Should we consider the time complexity here quadratic, cubic or as a different size complexity?

btilly :

Short answer, O(choose(N+k, N)) which is the same as O(choose(N+k, k)).


Here is the long answer for how to get there.

You have the basic question version correct. With k nested loops, your complexity is going to be O(N^k) as N goes to infinity. However as k and N both vary, the behavior is more complex.

Let's consider the opposite extreme. Suppose that N is fixed, and k varies. If N is 0, your time is constant because the outermost loop fails on the first iteration.. If N = 1 then your time is O(k) because you go through all of the levels of nesting with only one choice and only have one choice every time. If N = 2 then something more interesting happens, you go through the nesting over and over again and it takes time O(k^N). And in general, with fixed N the time is O(k^N) where one factor of k is due to the time taken to traverse the nesting, and O(k^(N-1)) being taken by where your sequence advances. This is an unexpected symmetry!

Now what happens if k and N are both big? What is the time complexity of that? Well here is something to give you intuition.

Can we describe all of the times that we arrive at the innermost loop? Yes! Consider k+N-1 slots With k of them being "entered one more loop" and N-1 of them being "we advanced the index by 1". I assert the following:

  1. These correspond 1-1 to the sequence of decisions by which we reached the innermost loop. As can be seen by looking at which indexes are bigger than others, and by how much.
  2. The "entered one more loop" entries at the end is work needed to get to the innermost loop for this iteration that did not lead to any other loop iterations.
  3. If 1 < N we actually need one more that that in unique work to get to the end.

Now this looks like a mess, but there is a trick that simplifies it quite unexpectedly.

The trick is this. Suppose that we took one of those patterns and inserted one extra "we advanced the index by 1" somewhere in that final stretch of "entered one more loop" entries at the end. How many ways are there to do that? The answer is that we can insert that last entry in between any two spots in that last stretch, including beginning and end, and there is one more way to do that than there are entries. In other words, the number of ways to do that matches how much unique work there was getting to this iteration!

什么手段是总的工作是成正比的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! )

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章