Формула сложности времени вложенных петель

Question

Я только начал эту стадию 2 Compsci Paper по алгоритмам, и все такое не является моей сильной точкой. Я столкнулся с этим на слайдах лекций.

int length = input.length();
for (int i = 0; i < length - 1; i++) {
    for (int j = i + 1; j < length; j++) {
        System.out.println(input.substring(i,j));
    }
}

«В каждой итерации внешний цикл выполняет $ frac {n^{2}-(2i-1) n-i+i^{2}} {2} $ Операции из внутреннего цикла для $ i = 0, Ldots, N-1 $. "

Кто -нибудь может объяснить мне это шаг за шагом?

Я полагаю, что формула выше была получена с использованием формулы Гаусса для добавления чисел ... Я думаю ...

Answer 1

Ваша интуиция верна, работа заключается в определении того, что вы объединяете.

Первый бит заключается в том, что печать цепочки длины $ M $ занимает операции $ M $, поэтому

System.out.println(input.substring(i,j));

Линия занимает операции $ ji $. (Примечание здесь заключается в том, что этот код в Java, если я не очень ошибаюсь, и substring(start, end) Метод дает подстроку, начиная с индекса start и заканчивая на end-1)

Итак, на каждой итерации внешней петли мы печатаем кучу подстроков, начиная с цепочки длины (только персонаж в индексе $ i $) и заканчивая подвеской, которая начинается с $ i $ и переходит к конец строки input.

Чтобы поместить это более математически, мы печатаем строки длины $ 1, 2, ldots, ni $. Поскольку количество операций, необходимых для печати строки, такое же, как и ее длина, мы выполняем операции $ sum_ {k = 1}^{ni} k $. Заменив формулу Гаусса на эту сумму, мы получаем, что количество операций равно: $$ frac {(ni) (n-i+1)} {2} $$

Затем умножение все дает формулу, которая у вас есть на слайдах.

Answer 2

Давайте работать снаружи в.

for (int i = 0; i < length - 1; i++) {

Ясно, что этот цикл выполняется $ n = mathtt {length} -1 $ times, поэтому мы получаем $ sum_ {i = 0}^{n-1} dots $, где $ dots $ стоит для времени, необходимого для Тело петли (для итерации $ i $). Внутри у нас есть

for (int j = i + 1; j < length; j++) {

который мы можем перевести аналогичным образом, получение $ sum_ {i = 0}^{n-1} sum_ {j = i+1}^{n} dots $. И последнее, но не менее важное, самая внутренняя операция

    System.out.println(input.substring(i,j));

По -видимому, предполагается, что он предпринимает шаги $ Ji $ (одна операция на символ).

Собрать все вместе, мы получаем

$ qquad begin {align} t (n) & = sum_ {i = 0}^{n -1} sum_ {j = i+1}^{n} j - i & = sum_ {{ i = 0}^{n -1} left [ left ( sum_ {j = i+1}^{n} j right) - (ni) i right] & = sum_ {i = 0}^{n -1} left [ left ( sum_ {j = 1}^{n} j - sum_ {j = 1}^{i} j right) - (ni) i right] & = sum_ {i = 0}^{n -1} left [ left ( frac {n (n+1)} {2} - frac {i (i+1)} {2} right) - (ni) i right] & = sum_ {i = 0}^{n -1} left [ frac {n^2 - (2i - 1) n + i^2 - i } {2} right] end {align} $

Термин в скобках - это то, что вы ищете.

Вся сумма может быть оценена с использованием формулы Гаусса и ее братья и сестра для Smell $ i^2 $:

$ qquad begin {align} 2t (n) & = sum_ {i = 0}^{n-1} n^2- sum_ {i = 0}^{n-1} 2in + sum_ {i = 0}^{n-1} n + sum_ {i = 0}^{n-1} i^2- sum_ {i = 0}^{n-1} i & = n^3- 2n cdot sum_ {i = 0}^{n-1} i + n^2 + sum_ {i = 0}^{n-1} i^2- sum_ {i = 0}^{n- 1} i & = n^3 - n^2 (n -1) + n^2 + frac {(n -1) n (2n - 1)} {6} - frac {n (n- 1)} {2} & = frac {12n^2 + 2n^3 - 3n^2 + n - 3n^2 + 3n} {6} & = frac {2n^3 + 6n^2 + 4n} {6} end {align} $

который немедленно дает

$ qquad displaystyle t (n) = frac {n^3 + 3n^2 + 2n} {6} $.