Временная сложность тройного вложенного цикла

13

Пожалуйста, рассмотрите следующую тройную вложенную петлю:

for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
        for (int k = j; k <= n; ++k)
            // statement

Здесь утверждение выполняется ровно раз Может кто-нибудь объяснить, как эта формула была получена? Спасибо.n(n+1)(n+2)6

Xin
источник
1
Вопрос формула сложности времени для вложенных циклов также может представлять интерес.
Юхо

Ответы:

14

Вы можете подсчитать, сколько раз выполняется самый внутренний цикл for, подсчитывая количество триплетов для которых он выполняется.(i,j,k)

По условиям цикла мы знаем, что: . Мы можем свести его к следующей простой проблеме комбинаторики.1ijkn

  • Представьте себе прямоугольника красного цвета, расположенных в массиве слева направо.n+2
  • Выберите любые 3 коробки из и покрасьте их в синий цвет.n+2
  • Сформируйте триплет следующим образом: (i,j,k)
    • = 1 + количество красных прямоугольников слева от первого синего поля.я
    • = 1 + количество красных прямоугольников слева от второго синего поля.J
    • = 1 + количество квадратов красного цвета слева от третьего синего поля.К

Итак, нам просто нужно посчитать количество способов выбора 3 блоков из блоков, что составляет ( n + 2N+2 .(N+23)

rizwanhudda
источник
2
Хороший ответ! Точные значения i, j, k не важны. Нам просто нужно знать, что любая синяя коробка может быть размещена в n возможных позициях и что их позиции ограничены: 2-й всегда идет после 1-го и до 3-го.
Давид Натингга
@rizwanhudda Очистить, кроме части в n + 2 . Можете ли вы объяснить это, пожалуйста? n + 3 выглядит как правильный номер. +2n+2n+3
saadtaame
1
@saadtaame Да. Вы можете вообразить, что у вас красных прямоугольника, но у вас есть свобода выбора 3 красных прямоугольников для рисования синим из числа « n + 2 красных прямоугольников», поскольку вы не можете покрасить первый прямоугольник в синий (так как i 1 )n+3n+2i1
rizwanhudda
3

для меня легче заметить, что внутренний цикл выполняется раз, а общее количество выполнений во внутреннем циклеni

(ni)+(ni1)+(ni2)++1

j=0ninijn

i=0nj=0ninij=n(n+1)(n+2)6
Энди Макевой
источник
Задача для вас: представьте, что у вас есть x-вложенный цикл. Согласно предыдущему ответу будет выполнено (n + x-1) выбор х раз. Как бы вы рассчитали свою формулу?
Давид Натингга
К счастью, ОП не попросил о вложении в x-nested! Как другой ответ, данный дан, расширяется до x-вложенного цикла? Мой ответ должен получить больше сумм от 0 до n, от 0 до n-i_1, от 0 до n-i_2, ..., от 0 до n-i_x. Но я не знаю, как это вычислить.
Энди Макевой
1
Ответ не раскрывается явно для общего x, но представленный процесс рассуждения легко проследить до x-вложенных циклов. Вы просто добавляете больше синих коробок. Я также не знаю, как бы я вычислил эти суммы.
Давид Натингга