Временная сложность простой части кода

Question

Вот простой фрагмент кода. Какова временная сложность?

for(int i=0;i<n;i++){ 
    String temp=""; 
    for(int j=i;j<n;j++){ 
     temp+=S.charAt(j); 
    } 
    System.out.println(temp); 
} 

N < = 5000

Код выше дает мне TLE, а следующий простой код дает мне Wrong Answer:

for(int i=0;i<n;i++){ 
    String temp =""; 
    for(int j=i;j<n;j++){ 

    } 
    System.out.println(temp); 
} 

Answer 1

Сложность фактически O(n^3), если игнорирование JIT оптимизация (и большинство возможных судей в сети отключает это). Начиная с 5000^3 ~= 1.2*10^11, ожидается получение TLE.

---

Объяснение временной сложности:

Посмотрите на свой код, и обратить особое внимание на комментарий я добавил:

for(int i=0;i<n;i++){ 
    String temp=""; 
    for(int j=i;j<n;j++){ 
     temp+=S.charAt(j); 
     // ^^ THIS IS NOT O(1)^^ 
    } 
    System.out.println(temp); 
} 

Каждая итерация внутренних петель занимает O(|temp|) время, где |temp| это длина temp.
Напомним, что String в java неизменен, а конкатция строк фактически создает новый объект при копировании старого базового char[], что приводит к линейной временной работе.

Итак, давайте рассмотрим длину temp.
Длина temp увеличивается на 1 для каждой итерации внутреннего контура и сбрасывается для каждой итерации внешнего контура.

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

Outer(n,i) = 1 + 2 + ... + n-i+1 = (n-i)(n-i+1)/2 

Теперь, подводя его итоги для всех значений i получает нас:

T(n) = sum {Outer(n,i) for i = 0,...,n} 
T(n) = (n-0)(n-0+1)/2 + (n-1)(n-1+1)/2 + ... + (n-n)(n-n+1)/2 
T(n) = n(n+1)(n+2)/6 

last equation - это вариант суммы квадратов.

Мы можем видеть, что T(n) действительно находится в O(n^3).

---

Это может быть значительно улучшено от O (N^3) в O (N^2) с использованием StringBuider