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

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

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!

0 条评论