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

Алгоритм, который проходит через все возможные последовательности индексов внутри массива.

Временная сложность одного цикла и является линейной и двух вложенных циклов является квадратичной 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):

введите описание изображения здесь введите описание изображения здесь

И так далее..

Должны ли мы рассматривать сложность времени здесь квадратичной, кубической или как сложность другого размера?

Всего 2 ответа


Для основных

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 <= и т. Д.


Короткий ответ, 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! ) choose(N+k, N) = (N+k)! / ( N! k! ) .


Есть идеи?

10000