Złożoność czasowa potrójnie zagnieżdżonej pętli

13

Proszę wziąć pod uwagę następującą potrójnie zagnieżdżoną pętlę:

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

Instrukcja tutaj wykonywana jest dokładnie razy. Czy ktoś mógłby wyjaśnić, w jaki sposób uzyskano ten wzór? Dziękuję Ci. $n(n+1)(n+2)\over6$

algorithms time-complexity algorithm-analysis

— Xin
źródło

1

Kwestia czasu formuła złożoność zagnieżdżonych pętli może być również interesujące.

— Juho

14

Możesz policzyć, ile razy wykonywana jest najbardziej wewnętrzna pętla, licząc liczbę trojaków dla których jest wykonywana. $(i,j,k)$

$1 \leq i \leq j \leq k \leq n$

$n+2$
$n+2$
- $i$
- $j$
- $k$

$n+2$ $n+2 \choose 3$

— rizwanhudda
źródło

2

Niezła odpowiedź! Dokładne wartości i, j, k nie są ważne. Musimy tylko wiedzieć, że dowolne niebieskie pole można umieścić w n możliwych pozycjach i że ich pozycje są ograniczone: 2. miejsce następuje zawsze po 1. i przed 3..

— Dávid Natingga

+ 2

$+2$

n + 2

$n+2$

n + 3

$n+3$

1

n + 3

$n+3$

n + 2

$n+2$

i \geq 1

$i \geq 1$

3

$n-i$

$(n-i)+(n-i-1)+(n-i-2)+\ldots+1$

$\sum_{j=0}^{n-i} n-i-j$ $n$

\sum_{i = 0}^{n} \sum_{j = 0}^{n - i} n - i - j = \frac{n (n + 1) (n + 2)}{6}

$\sum_{i=0}^{n}\sum_{j=0}^{n-i} n-i-j=\frac{n(n+1)(n+2)}{6}$

— Andy Mcevoy
źródło

Wyzwanie dla Ciebie: Wyobraź sobie, że masz pętlę zagnieżdżoną w kształcie litery X. Zgodnie z poprzednią odpowiedzią wykonałby (n + x-1) wybór x razy. Jak obliczysz swoją formułę?

— Dávid Natingga

na szczęście OP nie poprosił o x-nested! W jaki sposób druga podana odpowiedź rozwija się do pętli zagnieżdżonej? Moja odpowiedź powinna uzyskać więcej sum od 0 do n, 0 do n-i_1, 0 do n-i_2, ..., 0 do n-i_x. Ale nie wiedziałbym, jak to obliczyć.

— andy mcevoy,

1

Odpowiedź nie rozwija się wyraźnie dla ogólnego x, ale przedstawiony proces wnioskowania jest łatwy do naśladowania dla pętli zagnieżdżonych w x. Po prostu dodajesz więcej niebieskich pól. Nie wiem też, jak obliczyć te więcej kwot.

— Dávid Natingga