Какова временная сложность итерации по всем возможным последовательностям массива?

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.Это, в частности, где вы расширяете формулу дальше.

Обратите внимание, что все индексы могут быть отключены на один, я не обращал особого внимания на < против <= и т. Д.

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), где один фактор k обусловлен временем, затрачиваемым на прохождение вложения, и O(k^(N-1)) - тем, где продвигается ваша последовательность. Это неожиданная симметрия!

А что будет, если k и N оба большие? Какова временная сложность этого? Что ж, вот что дает вам интуицию.

Можем ли мы описать все времена, когда мы достигаем самой внутренней петли? Да! Рассмотрим k+N-1 слотов. k из них "вошли в еще один цикл" и N-1 из них ". Мы увеличили индекс на 1". Я утверждаю следующее :

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! ).