Как я могу найти сложность времени для внутренних циклов, которые зависят от «i» из внешнего цикла:

Question

как я могу найти временную сложность для внутренних циклов, которые зависят от "i" из внешнего цикла, например:

int sum = 0;
for(int i = 0; i < n * n; i++) {
    for(int j = n - 1; j >= n - 1 - i; j--) {
        sum = i + j;
        System.out.println(sum);
    }
}

У меня такое сложное время, чтобы выяснить сложность времени для этого.Я знаю, что если есть «я», мы используем правило суммирования, но как в этом случае это будет?

Answer 1

Внутренний цикл изменяется вместе с внешним циклом, поэтому он зависит.Вы не можете напрямую найти стоимость только внутреннего цикла.

for(int i = 0; i < n * n; i++) {              \\ \sum_{i=0}^{n^2}
    for(int j = n - 1; j >= n - 1 - i; j--) { \\  \sum_{n-1-i}^{n-1} 
        sum = i + j;                          \\      1
        System.out.println(sum);
    }
}

Итак, нам нужно решить

Answer 2

Внутренний цикл выполняет 1 итерацию в начале, увеличивая до n*n итераций к концу.

i       iterations of inner loop
-       ------------------------
0       1
1       2
2       3
...
n*n-2   n*n-1
n*n-1   n*n

Общее количество итераций внутреннего цикла является суммой этих:

или

Следовательно, сложность времени составляет Θ ( п ^{4 * * ** тысяча двадцать-одна 1022). * * +1023}